Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 30th, 2020 71 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top