Dang_Quan_10_Tin

DONGDIEN

Jun 19th, 2022 (edited)
949
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 2010;
  7. constexpr ll Inf = 0x7fffffff;
  8.  
  9. /* --- Find Maximum Flow --- */
  10.  
  11. vector<int> adj[N];
  12. int w[N][N];
  13. vector<int> sinklist;
  14. bool col[N];
  15. int par[N];
  16. int totflow, flow;
  17. int n, e;
  18.  
  19. void updategraph(int source, int sink)
  20. {
  21.     int prev, next;
  22.  
  23.     next = sink;
  24.     flow = Inf;
  25.    
  26.     while (par[next] > -1)
  27.     {
  28.         prev = par[next];
  29.         flow = min(flow, w[prev][next]);
  30.         next = prev;
  31.     }
  32.  
  33.     next = sink;
  34.  
  35.     while (par[next] > -1)
  36.     {
  37.         prev = par[next];
  38.         w[prev][next] -= flow;
  39.         w[next][prev] += flow;
  40.         next = prev;
  41.     }
  42. }
  43.  
  44. bool augment_path(int source, int sink)
  45. {
  46.     queue<int> q;
  47.     q.push(source);
  48.  
  49.     memset(par, -1, sizeof par);
  50.     memset(col, 0, sizeof col);
  51.     col[source] = true;
  52.  
  53.     int prev, next;
  54.     bool cnt = true;
  55.  
  56.     while (q.size() and cnt)
  57.     {
  58.         int i;
  59.         prev = q.front();
  60.         q.pop();
  61.  
  62.         for (i = 0; i < (int)adj[prev].size(); i++)
  63.         {
  64.             next = adj[prev][i];
  65.             if (!col[next] and w[prev][next] > 0)
  66.             {
  67.                 col[next] = true;
  68.                 par[next] = prev;
  69.                 if (next == sink)
  70.                     continue;
  71.                 q.push(next);
  72.             }
  73.         }
  74.     }
  75.     return par[sink] != -1;
  76. }
  77.  
  78. int maxflow(int source, int sink)
  79. {
  80.     totflow = 0;
  81.     sinklist = adj[sink];
  82.     while (augment_path(source, sink))
  83.     {
  84.         for (int i = 0; i < (int)sinklist.size(); i++)
  85.         {
  86.             int u = sinklist[i];
  87.  
  88.             if (!col[u] or w[u][sink] <= 0)
  89.                 continue;
  90.  
  91.             par[sink] = u;
  92.             updategraph(source, sink);
  93.             totflow += flow;
  94.         }
  95.     }
  96.     return totflow;
  97. }
  98.  
  99. void makeedge(int a, int b, int c)
  100. {
  101.     adj[a].push_back(b);
  102.     adj[b].push_back(a);
  103.     w[a][b] = c;
  104.     w[b][a] = 0;
  105. }
  106.  
  107. /* --- End Find Maximum Flow --- */
  108.  
  109. int r, c;
  110. int Row[60], Col[60];
  111.  
  112. void Solve()
  113. {
  114.     memset(w, 0, sizeof w);
  115.  
  116.     for (int i = 0; i < r + c + 10; i++)
  117.         adj[i].clear();
  118.  
  119.     int source = r + c + 2, sink = r + c + 3, t1 = r;
  120.     int sumr = 0, sumc = 0;
  121.  
  122.     for (int i = 0; i < r; i++)
  123.     {
  124.         cin >> Row[i];
  125.         sumr += Row[i];
  126.         makeedge(source, i, Row[i]);
  127.     }
  128.  
  129.     for (int j = 0; j < c; j++)
  130.     {
  131.         cin >> Col[j];
  132.         sumc += Col[j];
  133.         makeedge(j + t1, sink, Col[j]);
  134.     }
  135.  
  136.     if (sumc != sumr)
  137.     {
  138.         cout << "-1\n";
  139.         return;
  140.     }
  141.  
  142.     for (int i = 0; i < r; i++)
  143.         for (int j = 0; j < c; j++)
  144.             makeedge(i, j + t1, 1);
  145.  
  146.     maxflow(source, sink);
  147.  
  148.     if (totflow != sumc)
  149.     {
  150.         cout << "-1\n";
  151.         return;
  152.     }
  153.  
  154.     for (int i = 0; i < r; i++)
  155.     {
  156.         for (int j = 0; j < c; j++)
  157.         {
  158.             int what = w[j + t1][i];
  159.  
  160.             w[i][j + t1] = w[j + t1][i] = 0;
  161.  
  162.             if (what)
  163.             {
  164.                 w[source][i] = w[j + t1][sink] = 1;
  165.                 if (augment_path(source, sink))
  166.                 {
  167.                     updategraph(source, sink);
  168.                     what = 0;
  169.                 }
  170.                 else
  171.                     w[source][i] = w[j + t1][sink] = 0;
  172.             }
  173.             cout << what;
  174.         }
  175.     }
  176.     cout << "\n";
  177. }
  178.  
  179. int main()
  180. {
  181.     ios_base::sync_with_stdio(0);
  182.     cin.tie(0);
  183.     cout.tie(0);
  184.  
  185.     while (cin >> r >> c)
  186.     {
  187.         if (r == 0)
  188.             return 0;
  189.         Solve();
  190.     }
  191.  
  192.     return 0;
  193. }
Advertisement
Add Comment
Please, Sign In to add comment