Nik_Perepelov

Прикол Олегу

Nov 3rd, 2021 (edited)
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1.  
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7. int n;
  8. vector<vector<int>> g;
  9. const int inf = 1e9;
  10. int findpath( vector<int> &vis, int u, int t, int f) {
  11.     if (u == t) {
  12.         return f;
  13.     }
  14.     vis[u] = true;
  15.     for (int v = 0; v < n; v++) {
  16.         if (vis[v] == 0 && g[u][v]>0) {
  17.             int df = findpath(vis, v, t, min(f, g[u][v]));
  18.             if (df > 0) {
  19.                 g[u][v] -= df;
  20.                 g[v][u] += df;
  21.                 return df;
  22.             }
  23.         }
  24.     }
  25.     return 0;
  26. }
  27. int maxflow(int s, int t) {
  28.     for (int flow = 0;;) {
  29.         vector<int> viss(n);
  30.         int df = findpath(viss, s, t, inf);
  31.         if (df == 0) {
  32.             return flow;
  33.         }
  34.         flow += df;
  35.     }
  36. }
  37. int main()
  38. {
  39.     int m;
  40.     cin >> n >> m;
  41.     g = vector<vector<int>> (n, vector<int> (n));
  42.     for (int i = 0; i < m; i++) {
  43.         int a, b, c;
  44.         cin >> a >> b >> c;
  45.         a--;
  46.         b--;
  47.         g[a][b] = c;
  48.  
  49.     }
  50.     cout << maxflow(0, n - 1);
  51. }
  52.  
Add Comment
Please, Sign In to add comment