SHARE
TWEET

Untitled

a guest Feb 24th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Ford-Falkerson
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 10;
  7. int c[MAXN][MAXN], f[MAXN][MAXN];
  8. vector<int> from;
  9. int n, k;
  10.  
  11. void dfs(int v, int p = -1) {
  12.     from[v] = p;
  13.     if (v == n - 1) return;
  14.     for (int to = 0; to < n; to++) {
  15.         if (from[to] == -1 && c[v][to] - f[v][to] > 0) {
  16.             dfs(to, v);
  17.         }
  18.     }
  19. }
  20.  
  21. int main() {
  22.     cin >> n >> k;
  23.     int u, v, temp;
  24.     for (int i = 0; i < n; i++) {
  25.         cin >> u >> v >> temp;
  26.         u--; v--;
  27.         c[u][v] = temp;
  28.     }
  29.     while (true) {
  30.         from.assign(n, -1);
  31.         dfs(0);
  32.         if (from[n - 1] == -1) break;
  33.  
  34.         int mn = INT_MAX;
  35.         int now = n - 1;
  36.         while (now != 0) {
  37.             int pred = from[now];
  38.             mn = min(mn, c[pred][now] - f[pred][now]);
  39.             now = pred;
  40.         }
  41.  
  42.         now = n - 1;
  43.         while (now != 0) {
  44.             int pred = from[now];
  45.             f[pred][now] += mn;
  46.             f[now][pred] -= mn;
  47.             now = pred;
  48.         }
  49.     }
  50.     int res = 0;
  51.     for (int i = 0; i < n; i++) {
  52.         if (c[i][n - 1] > 0) res += f[i][n - 1];
  53.     }
  54.     cout << res;
  55.     return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top