peltorator

!l-r-циркуляция Диниц

Apr 19th, 2019
170
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, d[N];
  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 && d[u] == d[v] + 1)
  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. void add(int x, int y, int z)
  88. {
  89.     g[x].push_back(sz(e));
  90.     e.push_back(Edge(x, y, z, 0));
  91.     g[y].push_back(sz(e));
  92.     e.push_back(Edge(y, x, 0, 0));
  93. }
  94.  
  95. int solve()
  96. {
  97.     int n;
  98.     if (!(cin >> n))
  99.         return 1;
  100.     int m, s;
  101.     cin >> m;
  102.     s = n;
  103.     t = n + 1;
  104.     e.clear();
  105.     for (int i = 0; i <= t; i++)
  106.         g[i].clear();
  107.     val.clear();
  108.     ed.clear();
  109.     for (int i = 0; i < m; i++)
  110.     {
  111.         int x, y, l, r;
  112.         cin >> x >> y >> l >> r;
  113.         x--;
  114.         y--;
  115.         add(x, y, r - l);
  116.         add(s, y, l);
  117.         add(x, t, l);
  118.     }
  119.     ll flow = 0;
  120.     while (true)
  121.     {
  122.         for (int i = 0; i <= t; i++)
  123.             used[i] = 0, d[i] = INF;
  124.         d[s] = 0;
  125.         queue<int> q;
  126.         q.push(s);
  127.         while (q.size())
  128.         {
  129.             int v = q.front();
  130.             q.pop();
  131.             for (int it : g[v])
  132.             {
  133.                 int u = e[it].to, f = e[it].f, c = e[it].c;
  134.                 if (d[u] > d[v] + 1 && f < c)
  135.                 {
  136.                     d[u] = d[v] + 1;
  137.                     q.push(u);
  138.                 }
  139.             }
  140.         }
  141.         if (d[t] == INF)
  142.             break;
  143.         while (true)
  144.         {
  145.             for (int i = 0; i <= t; i++)
  146.             used[i] = 0;
  147.             int x = dfs(s, 1, INF);
  148.             if (!x)
  149.                 break;
  150.             else
  151.                 flow += x;
  152.         }
  153.     }
  154.     for (int i = 0; i < sz(e); i += 6)
  155.         if (e[i + 2].f != e[i + 2].c || e[i + 4].f != e[i + 4].c)
  156.         {
  157.             cout << "NO\n";
  158.             return 1;
  159.         }
  160.     cout << "YES\n";
  161.     for (int i = 0; i < sz(e); i += 6)
  162.         cout << e[i + 2].c + e[i].f << ' ';
  163.     cout << endl;
  164.     return 1;
  165. }
  166.  
  167. int32_t main()
  168. {
  169.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  170.     int TET = 1e9;
  171.     //cin >> TET;
  172.     while (TET--)
  173.     {
  174.         if (solve())
  175.             break;
  176.         #ifdef ONPC
  177.             cout << "\n__________________________" << endl;
  178.         #endif
  179.     }
  180.     #ifdef ONPC
  181.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  182.     #endif
  183.     return 0;
  184. }
RAW Paste Data