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, m;
- int maxFlow;
- vector<vector<int> > g;
- vector<vector<int> > flow;
- int findPath() {
- queue<int> q;
- vector<int> parent(n, -1);
- q.push(0);
- parent[0] = 0;
- while (!q.empty() && q.front() != n - 1) {
- 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[n - 1] == -1)
- return 0;
- else {
- int update = INT_MAX;
- for (int v = n - 1; v != 0; ) {
- int prev = parent[v];
- update = min(update, g[prev][v] - flow[prev][v]);
- v = prev;
- }
- for (int v = n - 1; v != 0; ) {
- int prev = parent[v];
- flow[prev][v] += update;
- flow[v][prev] -= update;
- v = prev;
- }
- return update;
- }
- }
- int main() {
- scanf("%d%d", &n, &m);
- g.resize(n, vector<int>(n, 0));
- flow.resize(n, vector<int>(n, 0));
- for (int i = 0; i < m; ++i) {
- int from, to, cost;
- scanf("%d%d%d", &from, &to, &cost);
- --from, --to;
- g[from][to] = cost;
- }
- int u;
- do {
- u = findPath();
- } while (u > 0);
- maxFlow = 0;
- for (int i = 0; i < n; ++i)
- if (g[0][i])
- maxFlow += flow[0][i];
- printf("%d\n", maxFlow);
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement