Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int n;
- vector<vector<int>> g;
- const int inf = 1e9;
- int findpath( vector<int> &vis, int u, int t, int f) {
- if (u == t) {
- return f;
- }
- vis[u] = true;
- for (int v = 0; v < n; v++) {
- if (vis[v] == 0 && g[u][v]>0) {
- int df = findpath(vis, v, t, min(f, g[u][v]));
- if (df > 0) {
- g[u][v] -= df;
- g[v][u] += df;
- return df;
- }
- }
- }
- return 0;
- }
- int maxflow(int s, int t) {
- for (int flow = 0;;) {
- vector<int> viss(n);
- int df = findpath(viss, s, t, inf);
- if (df == 0) {
- return flow;
- }
- flow += df;
- }
- }
- int main()
- {
- int m;
- cin >> n >> m;
- g = vector<vector<int>> (n, vector<int> (n));
- for (int i = 0; i < m; i++) {
- int a, b, c;
- cin >> a >> b >> c;
- a--;
- b--;
- g[a][b] = c;
- }
- cout << maxflow(0, n - 1);
- }
Add Comment
Please, Sign In to add comment