Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- constexpr int N = 2010;
- constexpr ll Inf = 0x7fffffff;
- /* --- Find Maximum Flow --- */
- vector<int> adj[N];
- int w[N][N];
- vector<int> sinklist;
- bool col[N];
- int par[N];
- int totflow, flow;
- int n, e;
- void updategraph(int source, int sink)
- {
- int prev, next;
- next = sink;
- flow = Inf;
- while (par[next] > -1)
- {
- prev = par[next];
- flow = min(flow, w[prev][next]);
- next = prev;
- }
- next = sink;
- while (par[next] > -1)
- {
- prev = par[next];
- w[prev][next] -= flow;
- w[next][prev] += flow;
- next = prev;
- }
- }
- bool augment_path(int source, int sink)
- {
- queue<int> q;
- q.push(source);
- memset(par, -1, sizeof par);
- memset(col, 0, sizeof col);
- col[source] = true;
- int prev, next;
- bool cnt = true;
- while (q.size() and cnt)
- {
- int i;
- prev = q.front();
- q.pop();
- for (i = 0; i < (int)adj[prev].size(); i++)
- {
- next = adj[prev][i];
- if (!col[next] and w[prev][next] > 0)
- {
- col[next] = true;
- par[next] = prev;
- if (next == sink)
- continue;
- q.push(next);
- }
- }
- }
- return par[sink] != -1;
- }
- int maxflow(int source, int sink)
- {
- totflow = 0;
- sinklist = adj[sink];
- while (augment_path(source, sink))
- {
- for (int i = 0; i < (int)sinklist.size(); i++)
- {
- int u = sinklist[i];
- if (!col[u] or w[u][sink] <= 0)
- continue;
- par[sink] = u;
- updategraph(source, sink);
- totflow += flow;
- }
- }
- return totflow;
- }
- void makeedge(int a, int b, int c)
- {
- adj[a].push_back(b);
- adj[b].push_back(a);
- w[a][b] = c;
- w[b][a] = 0;
- }
- /* --- End Find Maximum Flow --- */
- int r, c;
- int Row[60], Col[60];
- void Solve()
- {
- memset(w, 0, sizeof w);
- for (int i = 0; i < r + c + 10; i++)
- adj[i].clear();
- int source = r + c + 2, sink = r + c + 3, t1 = r;
- int sumr = 0, sumc = 0;
- for (int i = 0; i < r; i++)
- {
- cin >> Row[i];
- sumr += Row[i];
- makeedge(source, i, Row[i]);
- }
- for (int j = 0; j < c; j++)
- {
- cin >> Col[j];
- sumc += Col[j];
- makeedge(j + t1, sink, Col[j]);
- }
- if (sumc != sumr)
- {
- cout << "-1\n";
- return;
- }
- for (int i = 0; i < r; i++)
- for (int j = 0; j < c; j++)
- makeedge(i, j + t1, 1);
- maxflow(source, sink);
- if (totflow != sumc)
- {
- cout << "-1\n";
- return;
- }
- for (int i = 0; i < r; i++)
- {
- for (int j = 0; j < c; j++)
- {
- int what = w[j + t1][i];
- w[i][j + t1] = w[j + t1][i] = 0;
- if (what)
- {
- w[source][i] = w[j + t1][sink] = 1;
- if (augment_path(source, sink))
- {
- updategraph(source, sink);
- what = 0;
- }
- else
- w[source][i] = w[j + t1][sink] = 0;
- }
- cout << what;
- }
- }
- cout << "\n";
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- while (cin >> r >> c)
- {
- if (r == 0)
- return 0;
- Solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment