Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <climits>
- int main()
- {
- int n, m, sum1 = 0, sum2 = 0;
- std::cin >> n >> m;
- std::vector<std::vector<int> > c(n + m + 2, std::vector<int>(n + m + 2, 0));
- for (int i = 0; i < n; ++i)
- {
- int tmp;
- std::cin >> tmp;
- c[0][i + 1] = tmp;
- sum1 += tmp;
- for (int j = 0; j < m; ++j)
- {
- c[i + 1][n + j + 1] = 1;
- }
- }
- for (int j = 0; j < m; ++j)
- {
- int tmp;
- std::cin >> tmp;
- c[n + j + 1][n + m + 1] = tmp;
- sum2 += tmp;
- }
- if (sum1 != sum2)
- {
- std::cout << "impossible" << std::endl;
- return 0;
- }
- std::vector<std::vector<int> > f(c.size(), std::vector<int>(c.size()));
- for (; ; )
- {
- std::vector<int> from(c.size(), -1);
- std::vector<int> q(c.size());
- int h = 0, t = 0;
- q[t++] = 0;
- from[0] = 0;
- for (int cur; h < t; )
- {
- cur = q[h++];
- for (int v = 0; v < (int)c.size(); ++v)
- {
- if (from[v] == -1 && c[cur][v] - f[cur][v] > 0)
- {
- q[t++] = v;
- from[v] = cur;
- }
- }
- }
- if (from[c.size() - 1] == -1)
- {
- break;
- }
- int cf = INT_MAX;
- for (int cur = c.size() - 1; cur != 0; )
- {
- int prev = from[cur];
- cf = std::min(cf, c[prev][cur] - f[prev][cur]);
- cur = prev;
- }
- for (int cur = c.size() - 1; cur != 0; )
- {
- int prev = from[cur];
- f[prev][cur] += cf;
- f[cur][prev] -= cf;
- cur = prev;
- }
- }
- int flow = 0;
- for (int i = 0; i < (int)c.size(); ++i)
- {
- if (c[0][i])
- {
- flow += f[0][i];
- }
- }
- if (flow != sum1)
- {
- std::cout << "impossible" << std::endl;
- }
- else
- {
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- std::cout << f[i + 1][n + j + 1];
- }
- std::cout << std::endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment