Advertisement
Guest User

Untitled

a guest
Dec 13th, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.27 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <set>
  5. #include <vector>
  6. #include <string>
  7. #include <queue>
  8. #include <deque>
  9. #include <ctime>
  10. #include <algorithm>
  11. #include <stdio.h>
  12. #pragma warning(disable:4996)
  13.  
  14. using namespace std;
  15.  
  16. class mark
  17. {
  18. public:
  19. bool marked;
  20. int from, flow;
  21. mark()
  22. {
  23. marked = false;
  24. }
  25.  
  26. void set(int from, int flow)
  27. {
  28. marked = true;
  29. this->flow = flow;
  30. this->from = from;
  31. }
  32. };
  33.  
  34. int first_team[43];
  35. int second_team[43];
  36. int from[89];
  37. int c[89][89]; // 0 - s, 1 - 43 первый отдел, 44 - 86 - второй отдел, 87 - для незаселенных, 88 - t
  38. int f[89][89];
  39. double sourceP[89][89];
  40. double p[89][89];
  41. double D[89];
  42. mark marks[89];
  43.  
  44. int module(int a, int b)
  45. {
  46. return a > b ? a - b : b - a;
  47. }
  48.  
  49. bool bfs()
  50. {
  51. queue <int> que;
  52. marks[0].set(-1, INT32_MAX);
  53. que.push(0);
  54. for (int i = 1; i < 89; i++)
  55. marks[i].marked = false;
  56. while (!que.empty())
  57. {
  58. for (int i = 0; i < 89; i++)
  59. {
  60. if (!marks[i].marked && c[que.front()][i] - f[que.front()][i] > 0)
  61. {
  62. marks[i].set(que.front(), min(c[que.front()][i] - f[que.front()][i], marks[que.front()].flow));
  63. que.push(i);
  64. }
  65. }
  66. if (marks[88].marked)
  67. return true;
  68. que.pop();
  69. }
  70. return false;
  71. }
  72.  
  73. void fill(int diff)
  74. {
  75. for (int i = 0; i < 89; i++)
  76. for (int g = 0; g < 89; g++)
  77. c[i][g] = 0;
  78. for (int i = 0; i < 43; i++)
  79. {
  80. if (first_team[i])
  81. c[0][i + 1] = first_team[i];
  82. }
  83. for (int i = 0; i < 43; i++)
  84. if (first_team[i])
  85. {
  86. for (int g = 0; g < 43; g++)
  87. if (second_team[g])
  88. {
  89. c[i + 1][g + 44] = min(first_team[i], second_team[g]);
  90. }
  91. c[i + 1][87] = min(first_team[i], diff);
  92. }
  93. for (int i = 0; i < 43; i++)
  94. {
  95. if (second_team[i])
  96. c[i + 44][88] = second_team[i];
  97. }
  98. c[87][88] = diff;
  99. }
  100.  
  101. pair <int, int> dataRead()
  102. {
  103. for (int i = 0; i < 43; i++)
  104. {
  105. first_team[i] = 0;
  106. second_team[i] = 0;
  107. }
  108. FILE * file = fopen("input.txt", "r");
  109. char symbol;
  110. int value, count1 = 0, count2 = 0;
  111. do
  112. {
  113. fscanf(file, "%d", &value);
  114. first_team[value - 18]++;
  115. count1++;
  116. symbol = fgetc(file);
  117. } while (symbol != 10);
  118. while (fscanf(file, "%d", &value) != EOF)
  119. {
  120. second_team[value - 18]++;
  121. count2++;
  122. }
  123. return make_pair(count1, count2);
  124. }
  125.  
  126. void fillSource()
  127. {
  128. for (int i = 0; i < 89; i++)
  129. for (int g = 0; g < 89; g++)
  130. sourceP[i][g] = 0;
  131. for (int i = 0; i < 43; i++)
  132. {
  133. for (int g = 0; g < 43; g++)
  134. sourceP[i + 1][g + 44] = module(i, g);
  135. sourceP[i + 1][87] = double(i) / 2 + 9;
  136. }
  137. }
  138.  
  139. void fillP()
  140. {
  141. for (int i = 0; i < 89; i++)
  142. for (int g = 0; g < 89; g++)
  143. p[i][g] = INT32_MAX;
  144. for (int i = 0; i < 89; i++)
  145. {
  146. for (int g = 0; g < 89; g++)
  147. {
  148. if (f[i][g] > 0)
  149. {
  150. if (f[i][g] == c[i][g])
  151. p[i][g] = -sourceP[i][g];
  152. else
  153. {
  154. p[i][g] = -sourceP[i][g];
  155. p[g][i] = sourceP[i][g];
  156. }
  157. }
  158. else
  159. {
  160. if(c[i][g])
  161. p[g][i] = sourceP[i][g];
  162. }
  163. }
  164. }
  165. }
  166.  
  167. void fillD()
  168. {
  169. for (int i = 0; i < 89; i++)
  170. D[i] = INT32_MAX / 2;
  171. D[0] = 0;
  172. for (int i = 0; i < 89; i++)
  173. for (int first = 0; first < 89; first++)
  174. for (int second = 0; second < 89; second++)
  175. if (p[first][second] != INT32_MAX)
  176. if (D[second] > D[first] + p[first][second])
  177. {
  178. D[second] = D[first] + p[first][second];
  179. from[second] = first;
  180. }
  181. }
  182.  
  183. int isAnyContures()
  184. {
  185. fillD();
  186. for (int first = 0; first < 89; first++)
  187. for (int second = 0; second < 89; second++)
  188. if (p[first][second] != INT32_MAX)
  189. if (D[second] > D[first] + p[first][second])
  190. return first;
  191. return -1;
  192. }
  193.  
  194. int findEnter(int begin)
  195. {
  196. int curr = begin;
  197. bool visited[89];
  198. for (int i = 0; i < 89; i++)
  199. visited[i] = false;
  200. while (!visited[curr])
  201. {
  202. visited[curr] = true;
  203. curr = from[curr];
  204. }
  205. return curr;
  206. }
  207.  
  208. int main()
  209. {
  210. ofstream out("output.txt");
  211. pair <int, int> count;
  212. int flow, curr, begin, total = 0, d = INT32_MAX;
  213. long double cost = 0;
  214. count = dataRead();
  215. if (count.first < count.second)
  216. {
  217. swap(first_team, second_team);
  218. count = make_pair(count.second, count.first);
  219. }
  220. fill(count.first - count.second);
  221. fillSource();
  222. while (bfs())
  223. {
  224. flow = marks[88].flow;
  225. total += flow;
  226. curr = 88;
  227. while (curr != -1)
  228. {
  229. marks;
  230. f[marks[curr].from][curr] += flow;
  231. f[curr][marks[curr].from] -= flow;
  232. curr = marks[curr].from;
  233. }
  234. }
  235. fillP();
  236. while ((begin = isAnyContures()) != -1)
  237. {
  238. d = INT32_MAX;
  239. begin = findEnter(begin);
  240. curr = begin;
  241. do
  242. {
  243. if (p[from[curr]][curr] < 0)
  244. {
  245. if (f[from[curr]][curr] < d)
  246. d = f[from[curr]][curr];
  247. }
  248. else
  249. {
  250. if (c[curr][from[curr]] - f[curr][from[curr]] < d)
  251. d = c[curr][from[curr]] - f[curr][from[curr]];
  252. }
  253. curr = from[curr];
  254. } while (curr != begin);
  255. curr = begin;
  256. do
  257. {
  258. if (p[from[curr]][curr] < 0)
  259. f[from[curr]][curr] -= d;
  260. else
  261. f[curr][from[curr]] += d;
  262. curr = from[curr];
  263. } while (curr != begin);
  264. fillP();
  265. }
  266. for (int i = 0; i < 89; i++)
  267. for (int g = 0; g < 89; g++)
  268. if (f[i][g] > 0)
  269. cost += sourceP[i][g] * f[i][g];
  270. long long int fullPart = int(cost);
  271. out << fullPart;
  272. if (cost - fullPart != 0)
  273. out << ".5";
  274. else
  275. out << ".0";
  276. return 0;
  277. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement