peltorator

!Декомпозиция Потока

May 5th, 2019
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifdef ONPC
  2.     # define _GLIBCXX_DEBUG
  3.     #define deb(a) cerr << "========" << #a << " = " << a << endl;
  4. #else
  5.     #define deb(a)
  6. #endif
  7. #define sz(a) (int)(a).size()
  8.  
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  14.  
  15. typedef long long ll;
  16.  
  17. struct Edge
  18. {
  19.     int from, to, c, f;
  20.     Edge(int from, int to, int c, int f):
  21.         from(from),
  22.         to(to),
  23.         c(c),
  24.         f(f) {}
  25. };
  26.  
  27. const int N = 100005;
  28. const int INF = 1e9 + 7;
  29. vector<Edge> e;
  30. vector<int> g[N];
  31. int used[N], t;
  32.  
  33.  
  34. void upd(int ind, int f)
  35. {
  36.     e[ind].f += f;
  37.     e[ind ^ 1].f -= f;
  38. }
  39.  
  40. int dfs(int v, int can, int cur)
  41. {
  42.     if (v == t)
  43.         return cur;
  44.     used[v] = 1;
  45.     for (int ind : g[v])
  46.     {
  47.         int u = e[ind].to, f = e[ind].f, c = e[ind].c;
  48.         if (!used[u] &&  c - f >= can)
  49.         {
  50.             int len = dfs(u, can, min(cur, c - f));
  51.             if (len)
  52.             {
  53.                 upd(ind, len);
  54.                 return len;
  55.             }
  56.         }
  57.     }
  58.     return 0;
  59. }
  60.  
  61. vector<int> val;
  62. vector<vector<int> > ed;
  63.  
  64.  
  65. int dfs2(int v, int cur)
  66. {
  67.     if (v == t)
  68.         return cur;
  69.     used[v] = 1;
  70.     for (int ind : g[v])
  71.     {
  72.         int u = e[ind].to, f = e[ind].f;
  73.         if (!used[u] && f > 0)
  74.         {
  75.             int len = dfs2(u, min(cur, f));
  76.             if (len)
  77.             {
  78.                 ed.back().push_back(ind);
  79.                 upd(ind, -len);
  80.                 return len;
  81.             }
  82.         }
  83.     }
  84.     return 0;
  85. }
  86.  
  87. int solve()
  88. {
  89.     int n;
  90.     if (!(cin >> n))
  91.         return 1;
  92.     int m, s;
  93.     cin >> m;
  94.     s = 0;
  95.     t = n - 1;
  96.     e.clear();
  97.     for (int i = 0; i < n; i++)
  98.         g[i].clear();
  99.     val.clear();
  100.     ed.clear();
  101.     for (int i = 0; i < m; i++)
  102.     {
  103.         int x, y, z;
  104.         cin >> x >> y >> z;
  105.         x--;
  106.         y--;
  107.         g[x].push_back(sz(e));
  108.         e.push_back(Edge(x, y, z, 0));
  109.         g[y].push_back(sz(e));
  110.         e.push_back(Edge(y, x, 0, 0));
  111.     }
  112.     for (int k = 30; k >= 0; k--)
  113.         while (true)
  114.         {
  115.             for (int i = 0; i < n; i++)
  116.                 used[i] = 0;
  117.             int x = dfs(s, (1 << k), INF);
  118.             if (!x)
  119.                 break;
  120.         }
  121.     while (true)
  122.     {
  123.         for (int i = 0; i < n; i++)
  124.             used[i] = 0;
  125.         ed.push_back(vector<int>(0));
  126.         val.push_back(dfs2(s, INF));
  127.         if (!val.back())
  128.             break;
  129.     }
  130.     val.pop_back();
  131.     ed.pop_back();
  132.     cout << sz(val) << endl;
  133.     for (int i = 0; i < sz(val); i++)
  134.     {
  135.         cout << val[i] << ' ' << sz(ed[i]) << ' ';
  136.         reverse(ed[i].begin(), ed[i].end());
  137.         for (int j : ed[i])
  138.             cout << j / 2 + 1 << ' ';
  139.         cout << '\n';
  140.     }
  141.     return 1;
  142. }
  143.  
  144. int32_t main()
  145. {
  146.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  147.     int TET = 1e9;
  148.     //cin >> TET;
  149.     while (TET--)
  150.     {
  151.         if (solve())
  152.             break;
  153.         #ifdef ONPC
  154.             cout << "\n__________________________" << endl;
  155.         #endif
  156.     }
  157.     #ifdef ONPC
  158.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  159.     #endif
  160.     return 0;
  161. }
RAW Paste Data