Advertisement
keker123

Untitled

Dec 16th, 2023 (edited)
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. const int X = 1e5 + 20;
  9. const int Inf = 1e9 + 7;
  10. int p;
  11. struct Edge {
  12.  
  13. Edge() = default;
  14.  
  15. Edge(int x, int c, int cap, int ind) : to(x), cost(c), capacity(cap), reverse(ind), flow(0) {};
  16.  
  17. int to;
  18. int cost;
  19. int capacity;
  20. int reverse;
  21. int flow;
  22. };
  23.  
  24. vector<Edge> edges;
  25.  
  26. vector<int> g[X];
  27. vector<int> dists(X, Inf);
  28. vector<int> P(X, 0);
  29.  
  30. int delta(Edge k) {
  31. return k.capacity - k.flow;
  32. }
  33.  
  34. void add(int v, int u, int c = 0, int cap = 1) {
  35. Edge x(u, c, cap, edges.size() + 1);
  36. Edge y(v, -c, 0, edges.size());
  37. g[v].push_back(edges.size());
  38. g[u].push_back(edges.size() + 1);
  39. edges.push_back(x);
  40. edges.push_back(y);
  41. }
  42.  
  43. bool dj(int s, int t) {
  44. dists.assign(X, Inf);
  45. set<pair<int, int>> d;
  46. d.insert({0, s});
  47. dists[s] = 0;
  48. while (!d.empty()) {
  49. auto x = *d.begin();
  50. int v = x.second;
  51. for (auto to: g[v]) {
  52. auto &e = edges[to];
  53. if (delta(e)) {
  54. int x = dists[v] + e.cost + P[v] - P[e.to];
  55. if (dists[e.to] > x) {
  56. d.erase({dists[e.to], e.to});
  57. dists[e.to] = x;
  58. d.insert({x, e.to});
  59.  
  60. }
  61. }
  62. }
  63. d.erase(d.begin());
  64. }
  65. for (int i = 0; i < X; i++) {
  66. if (dists[i] != Inf) {
  67. P[i] += dists[i];
  68. }
  69. }
  70. return dists[t] < Inf;
  71. }
  72.  
  73.  
  74. int dfsW(int v, int t, vector<bool> &used, int fl = Inf) {
  75. if (v == t) {
  76. return fl == Inf ? 0 : fl;
  77. }
  78. used[v] = true;
  79. for (auto to: g[v]) {
  80. auto &e = edges[to];
  81. if (!used[e.to] && delta(e) && e.cost + P[v] - P[e.to] == 0) {
  82. int x = dfsW(e.to, t, used, min(fl, delta(e)));
  83. if (x) {
  84. e.flow += x;
  85. edges[e.reverse].flow -= x;
  86. return x;
  87. }
  88. }
  89. }
  90. return 0;
  91. }
  92.  
  93. pair<int, int> MCMF(int s, int t) {
  94. vector<bool> used(X, false);
  95. int ans = 0;
  96. while (dj(s, t)) {
  97. dfsW(s, t, used);
  98. used.assign(X, false);
  99. }
  100.  
  101. for (int i = 0; i < X; i++) {
  102. for (auto to: g[i]) {
  103. auto &e = edges[to];
  104. ans += e.flow * e.cost;
  105. }
  106. }
  107.  
  108. int flow = 0;
  109. for (auto x : g[s]) {
  110. auto k = edges[x];
  111. flow += k.flow;
  112. }
  113.  
  114. return {flow, ans / 2};
  115. }
  116.  
  117. int main() {
  118. int n, m, k;
  119. cin >> n >> m >> k;
  120. cin >> p;
  121. int e1, e2;
  122. cin >> e1 >> e2;
  123. int size = n + 2 * m + k + 3;
  124.  
  125. int Boots = 0;
  126. int PantsIn = n;
  127. int PantsOut = n + m;
  128. int Tunics = n + 2*m;
  129.  
  130. vector<int> boots(n + 1);
  131. for (int i = 1; i <= n; ++i) {
  132. cin >> boots[i];
  133. add(0, i, boots[i]);
  134. }
  135. vector<int> pants(m + 1);
  136.  
  137. for (int i = 1; i <= m; ++i) { // раздваиваем вершины
  138. cin >> pants[i];
  139. add(PantsIn + i, PantsOut + i);
  140. }
  141.  
  142. vector<int> tunics(k + 1);
  143. for (int i = 1; i <= k; ++i) {
  144. cin >> tunics[i];
  145. add(Tunics + i, size - 2);
  146. }
  147.  
  148. int a, b;
  149. for (int i = 0; i < e1; ++i) {
  150. cin >> a >> b;
  151. add(PantsOut + a, Tunics + b, tunics[b]);
  152. }
  153.  
  154. for (int i = 0; i < e2; ++i) {
  155. cin >> a >> b;
  156. add(Boots + b, PantsIn + a, pants[a]);
  157. }
  158. add(size - 2, size - 1, 0, p);
  159.  
  160. auto result = MCMF(0, size - 1);
  161.  
  162. if (result.first < p) {
  163. cout << -1 << endl;
  164. return 0;
  165. }
  166.  
  167. cout << result.second << endl;
  168. }
  169.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement