Advertisement
Guest User

MaxFlow

a guest
Nov 22nd, 2014
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <climits>
  9.  
  10. using namespace std;
  11.  
  12. int n, m;
  13. int maxFlow;
  14. vector<vector<int> > g;
  15. vector<vector<int> > flow;
  16.  
  17. int findPath() {
  18.     queue<int> q;
  19.     vector<int> parent(n, -1);
  20.  
  21.     q.push(0);
  22.     parent[0] = 0;
  23.    
  24.     while (!q.empty() && q.front() != n - 1) {
  25.         int from = q.front(); q.pop();
  26.  
  27.         for (int i = 0; i < n; ++i)
  28.             if (g[from][i] - flow[from][i] > 0 && parent[i] == -1) {
  29.                 q.push(i); parent[i] = from;
  30.             }
  31.     }
  32.  
  33.     if (parent[n - 1] == -1)
  34.         return 0;
  35.     else {
  36.         int update = INT_MAX;
  37.         for (int v = n - 1; v != 0; ) {
  38.             int prev = parent[v];
  39.             update = min(update, g[prev][v] - flow[prev][v]);
  40.             v = prev;
  41.         }
  42.  
  43.         for (int v = n - 1; v != 0; ) {
  44.             int prev = parent[v];
  45.             flow[prev][v] += update;
  46.             flow[v][prev] -= update;
  47.             v = prev;
  48.         }
  49.  
  50.         return update;
  51.     }
  52. }
  53.  
  54. int main() {
  55.     scanf("%d%d", &n, &m);
  56.     g.resize(n, vector<int>(n, 0));
  57.     flow.resize(n, vector<int>(n, 0));
  58.  
  59.     for (int i = 0; i < m; ++i) {
  60.         int from, to, cost;
  61.         scanf("%d%d%d", &from, &to, &cost);
  62.  
  63.         --from, --to;
  64.         g[from][to] = cost;
  65.     }
  66.  
  67.     int u;
  68.     do {
  69.         u = findPath();
  70.     } while (u > 0);
  71.  
  72.     maxFlow = 0;
  73.     for (int i = 0; i < n; ++i)
  74.         if (g[0][i])
  75.             maxFlow += flow[0][i];
  76.  
  77.     printf("%d\n", maxFlow);
  78.    
  79.     system("pause");
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement