Guest User

Untitled

a guest
Mar 30th, 2020
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int M = 409;
  7. const int N = 109;
  8. const ll INF = (ll)1e18;
  9.  
  10. struct edge {
  11. int v, u;
  12. ll w;
  13.  
  14. edge() {
  15. v = 0;
  16. u = 0;
  17. w = 0;
  18. }
  19.  
  20. edge(int v, int u, ll w) : v(v), u(u), w(w) {}
  21. };
  22.  
  23. int n, m;
  24. edge e[M * 2 + 100];
  25. ll ans[M * 2 + 100];
  26. vector <pair<ll, int>> g[N];
  27.  
  28. bool used[N];
  29.  
  30. ll dfs(int v, ll minW) {
  31. used[v] = true;
  32.  
  33. if (v == n - 1) {
  34. return minW;
  35. }
  36.  
  37. for (auto x : g[v]) {
  38. ll sign = x.first;
  39. auto vu_edge = e[x.second];
  40. int u = vu_edge.u;
  41. ll w = vu_edge.w - abs(ans[x.second]);
  42.  
  43. if (used[u])
  44. continue;
  45.  
  46. if (w == 0)
  47. continue;
  48.  
  49. ll ret = dfs(u, min(minW, w));
  50.  
  51. if (ret != 0) {
  52. ans[x.second] += ret * sign;
  53. return ret;
  54. }
  55. }
  56.  
  57. return 0;
  58. }
  59.  
  60. set <int> minCut;
  61.  
  62. void findMinCut(int v) {
  63. used[v] = true;
  64.  
  65. for (auto x : g[v]) {
  66. ll sign = x.first;
  67. auto vu_edge = e[x.second];
  68. int u = vu_edge.u;
  69. ll w = ans[x.second % m] + ans[x.second % m + m];
  70. w *= sign;
  71. //cout << v + 1 << " -> " << u + 1 << " | " << w << " ~ " << vu_edge.w << "\n";
  72. if (used[u])
  73. continue;
  74.  
  75. if (w == vu_edge.w)
  76. continue;
  77.  
  78. findMinCut(u);
  79. }
  80. }
  81.  
  82. int main() {
  83. //freopen("out.txt", "r", stdin);
  84.  
  85. cin >> n >> m;
  86.  
  87. int a, b;
  88. ll c;
  89.  
  90. for (int i = 0; i < m; i++) {
  91. cin >> a >> b >> c;
  92.  
  93. a--;
  94. b--;
  95.  
  96. e[i] = edge(a, b, c);
  97. e[i + m] = edge(b, a, c);
  98.  
  99. g[a].push_back({1, i});
  100. g[b].push_back({-1, i + m});
  101. }
  102.  
  103. while(dfs(0, INF) != 0) {
  104. fill(used, used + N, false);
  105. }
  106.  
  107. ll maxFlow = 0;
  108.  
  109. for (auto x : g[0]) {
  110. maxFlow += abs(ans[x.second]);
  111. }
  112.  
  113. fill(used, used + N, false);
  114.  
  115. findMinCut(0);
  116.  
  117. for (int i = 0; i < n; i++) {
  118. if (!used[i])
  119. continue;
  120.  
  121. for (auto x : g[i]) {
  122. if (used[e[x.second].u])
  123. continue;
  124. /*
  125. if ((ans[x.second % m] + ans[x.second % m + m]) * x.first <= 0)
  126. continue;
  127. */
  128. minCut.insert(x.second % m);
  129. }
  130. }
  131.  
  132. cout << minCut.size() << " " << maxFlow << "\n";
  133.  
  134. for (int x : minCut) {
  135. cout << x + 1 << " ";
  136. }
  137.  
  138. return 0;
  139. }
  140.  
  141. /*
  142. 7 8
  143. 1 2 3
  144. 1 3 2
  145. 4 3 2
  146. 2 4 3
  147. 4 5 2
  148. 6 4 3
  149. 7 6 2
  150. 7 5 3
  151.  
  152.  
  153. 4 5
  154. 1 2 10000000
  155. 3 1 1
  156. 3 2 10000
  157. 3 4 100000
  158. 4 2 100000
  159.  
  160.  
  161. */
RAW Paste Data