Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <fstream>
- #include <set>
- #include <vector>
- #include <string>
- #include <queue>
- #include <deque>
- #include <ctime>
- #include <algorithm>
- #include <stdio.h>
- #pragma warning(disable:4996)
- using namespace std;
- class mark
- {
- public:
- bool marked;
- int from, flow;
- mark()
- {
- marked = false;
- }
- void set(int from, int flow)
- {
- marked = true;
- this->flow = flow;
- this->from = from;
- }
- };
- int first_team[43];
- int second_team[43];
- int from[89];
- int c[89][89]; // 0 - s, 1 - 43 первый отдел, 44 - 86 - второй отдел, 87 - для незаселенных, 88 - t
- int f[89][89];
- double sourceP[89][89];
- double p[89][89];
- double D[89];
- mark marks[89];
- int module(int a, int b)
- {
- return a > b ? a - b : b - a;
- }
- bool bfs()
- {
- queue <int> que;
- marks[0].set(-1, INT32_MAX);
- que.push(0);
- for (int i = 1; i < 89; i++)
- marks[i].marked = false;
- while (!que.empty())
- {
- for (int i = 0; i < 89; i++)
- {
- if (!marks[i].marked && c[que.front()][i] - f[que.front()][i] > 0)
- {
- marks[i].set(que.front(), min(c[que.front()][i] - f[que.front()][i], marks[que.front()].flow));
- que.push(i);
- }
- }
- if (marks[88].marked)
- return true;
- que.pop();
- }
- return false;
- }
- void fill(int diff)
- {
- for (int i = 0; i < 89; i++)
- for (int g = 0; g < 89; g++)
- c[i][g] = 0;
- for (int i = 0; i < 43; i++)
- {
- if (first_team[i])
- c[0][i + 1] = first_team[i];
- }
- for (int i = 0; i < 43; i++)
- if (first_team[i])
- {
- for (int g = 0; g < 43; g++)
- if (second_team[g])
- {
- c[i + 1][g + 44] = min(first_team[i], second_team[g]);
- }
- c[i + 1][87] = min(first_team[i], diff);
- }
- for (int i = 0; i < 43; i++)
- {
- if (second_team[i])
- c[i + 44][88] = second_team[i];
- }
- c[87][88] = diff;
- }
- pair <int, int> dataRead()
- {
- for (int i = 0; i < 43; i++)
- {
- first_team[i] = 0;
- second_team[i] = 0;
- }
- FILE * file = fopen("input.txt", "r");
- char symbol;
- int value, count1 = 0, count2 = 0;
- do
- {
- fscanf(file, "%d", &value);
- first_team[value - 18]++;
- count1++;
- symbol = fgetc(file);
- } while (symbol != 10);
- while (fscanf(file, "%d", &value) != EOF)
- {
- second_team[value - 18]++;
- count2++;
- }
- return make_pair(count1, count2);
- }
- void fillSource()
- {
- for (int i = 0; i < 89; i++)
- for (int g = 0; g < 89; g++)
- sourceP[i][g] = 0;
- for (int i = 0; i < 43; i++)
- {
- for (int g = 0; g < 43; g++)
- sourceP[i + 1][g + 44] = module(i, g);
- sourceP[i + 1][87] = double(i) / 2 + 9;
- }
- }
- void fillP()
- {
- for (int i = 0; i < 89; i++)
- for (int g = 0; g < 89; g++)
- p[i][g] = INT32_MAX;
- for (int i = 0; i < 89; i++)
- {
- for (int g = 0; g < 89; g++)
- {
- if (f[i][g] > 0)
- {
- if (f[i][g] == c[i][g])
- p[i][g] = -sourceP[i][g];
- else
- {
- p[i][g] = -sourceP[i][g];
- p[g][i] = sourceP[i][g];
- }
- }
- else
- {
- if(c[i][g])
- p[g][i] = sourceP[i][g];
- }
- }
- }
- }
- void fillD()
- {
- for (int i = 0; i < 89; i++)
- D[i] = INT32_MAX / 2;
- D[0] = 0;
- for (int i = 0; i < 89; i++)
- for (int first = 0; first < 89; first++)
- for (int second = 0; second < 89; second++)
- if (p[first][second] != INT32_MAX)
- if (D[second] > D[first] + p[first][second])
- {
- D[second] = D[first] + p[first][second];
- from[second] = first;
- }
- }
- int isAnyContures()
- {
- fillD();
- for (int first = 0; first < 89; first++)
- for (int second = 0; second < 89; second++)
- if (p[first][second] != INT32_MAX)
- if (D[second] > D[first] + p[first][second])
- return first;
- return -1;
- }
- int findEnter(int begin)
- {
- int curr = begin;
- bool visited[89];
- for (int i = 0; i < 89; i++)
- visited[i] = false;
- while (!visited[curr])
- {
- visited[curr] = true;
- curr = from[curr];
- }
- return curr;
- }
- int main()
- {
- ofstream out("output.txt");
- pair <int, int> count;
- int flow, curr, begin, total = 0, d = INT32_MAX;
- long double cost = 0;
- count = dataRead();
- if (count.first < count.second)
- {
- swap(first_team, second_team);
- count = make_pair(count.second, count.first);
- }
- fill(count.first - count.second);
- fillSource();
- while (bfs())
- {
- flow = marks[88].flow;
- total += flow;
- curr = 88;
- while (curr != -1)
- {
- marks;
- f[marks[curr].from][curr] += flow;
- f[curr][marks[curr].from] -= flow;
- curr = marks[curr].from;
- }
- }
- fillP();
- while ((begin = isAnyContures()) != -1)
- {
- d = INT32_MAX;
- begin = findEnter(begin);
- curr = begin;
- do
- {
- if (p[from[curr]][curr] < 0)
- {
- if (f[from[curr]][curr] < d)
- d = f[from[curr]][curr];
- }
- else
- {
- if (c[curr][from[curr]] - f[curr][from[curr]] < d)
- d = c[curr][from[curr]] - f[curr][from[curr]];
- }
- curr = from[curr];
- } while (curr != begin);
- curr = begin;
- do
- {
- if (p[from[curr]][curr] < 0)
- f[from[curr]][curr] -= d;
- else
- f[curr][from[curr]] += d;
- curr = from[curr];
- } while (curr != begin);
- fillP();
- }
- for (int i = 0; i < 89; i++)
- for (int g = 0; g < 89; g++)
- if (f[i][g] > 0)
- cost += sourceP[i][g] * f[i][g];
- long long int fullPart = int(cost);
- out << fullPart;
- if (cost - fullPart != 0)
- out << ".5";
- else
- out << ".0";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement