Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 300;
  7. const int inf = 1'000'000'000;
  8.  
  9. int n;
  10. int S, T;
  11. int M[N][N]; // из i-го в j-ое ребро пропускная способность
  12. bool F[N];
  13.  
  14. int dfs(int v, int c = inf) {
  15.     if (v == T) {
  16.         return c;
  17.     }
  18.     F[v] = true;
  19.     for (int a = 1; a <= n; a++) {
  20.         if (M[v][a] > 0 && !F[a]) {
  21.             int t = dfs(a, min(c, M[v][a]));
  22.             if (t > 0) {
  23.                 M[v][a] -= t;
  24.                 M[a][v] += t;
  25.                 return t;
  26.             }
  27.         }
  28.     }
  29.     return 0;
  30. }
  31.  
  32. int main() {
  33.     cin >> n;
  34.     cin >> S >> T;
  35.     for (int i = 1; i <= n; i++) {
  36.         for (int j = 1; j <= n; j++) {
  37.             cin >> M[i][j];
  38.         }
  39.     }
  40.     int max_flow = 0;
  41.     while (true) {
  42.         for (int i = 1; i <= n; i++) {
  43.             F[i] = false;
  44.         }
  45.         int flow = dfs(S);
  46.         max_flow += flow;
  47.         if (flow == 0) {
  48.             break;
  49.         }
  50.     }
  51.     cout << max_flow;
  52.     return 0;
  53. }
  54.  
  55. /*
  56. 7
  57. 1 7
  58. 0 3 0 0 2 0 0
  59. 0 0 2 1 0 0 0
  60. 0 0 0 0 0 0 4
  61. 0 0 0 0 0 0 3
  62. 0 0 0 0 0 5 0
  63. 0 0 0 0 0 0 1
  64. 0 0 0 0 0 0 0
  65. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement