Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <queue>
- #include <map>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <climits>
- using namespace std;
- int n, s, t;
- int maxFlow;
- vector<vector<int> > g;
- vector<vector<int> > flow;
- int findPath() {
- queue<int> q;
- vector<int> parent(n, -1);
- q.push(s);
- parent[s] = 0;
- while (!q.empty() && q.front() != t) {
- int from = q.front(); q.pop();
- for (int i = 0; i < n; ++i)
- if (g[from][i] - flow[from][i] > 0 && parent[i] == -1) {
- q.push(i); parent[i] = from;
- }
- }
- if (parent[t] == -1)
- return 0;
- else {
- int update = INT_MAX;
- for (int v = t; v != 0; ) {
- int prev = parent[v];
- update = min(update, g[prev][v] - flow[prev][v]);
- v = prev;
- }
- for (int v = t; v != 0; ) {
- int prev = parent[v];
- flow[prev][v] += update;
- flow[v][prev] -= update;
- v = prev;
- }
- return update;
- }
- }
- int main() {
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- scanf("%d", &n);
- g.resize(n, vector<int>(n, 0));
- flow.resize(n, vector<int>(n, 0));
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < n; ++j)
- scanf("%d", &g[j][i]);
- scanf("%d%d", &s, &t);
- --s, --t;
- int u;
- do {
- u = findPath();
- } while (u > 0);
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j)
- printf("%d ", max(flow[j][i], 0));
- putchar('\n');
- }
- maxFlow = 0;
- for (int i = 0; i < n; ++i)
- if (g[i][t])
- maxFlow += flow[i][t];
- printf("%d\n", maxFlow);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement