Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 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, s, t;
  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(s);
  22.     parent[s] = 0;
  23.  
  24.     while (!q.empty() && q.front() != t) {
  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[t] == -1)
  34.         return 0;
  35.     else {
  36.         int update = INT_MAX;
  37.         for (int v = t; 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 = t; 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.   freopen("in.txt", "r", stdin);
  56.   freopen("out.txt", "w", stdout);
  57.  
  58.     scanf("%d", &n);
  59.     g.resize(n, vector<int>(n, 0));
  60.     flow.resize(n, vector<int>(n, 0));
  61.  
  62.     for (int i = 0; i < n; ++i)
  63.     for (int j = 0; j < n; ++j)
  64.       scanf("%d", &g[j][i]);
  65.  
  66.     scanf("%d%d", &s, &t);
  67.     --s, --t;
  68.  
  69.     int u;
  70.     do {
  71.         u = findPath();
  72.     } while (u > 0);
  73.  
  74.     for (int i = 0; i < n; ++i) {
  75.         for (int j = 0; j < n; ++j)
  76.             printf("%d ", max(flow[j][i], 0));
  77.         putchar('\n');
  78.     }
  79.  
  80.     maxFlow = 0;
  81.     for (int i = 0; i < n; ++i)
  82.         if (g[i][t])
  83.             maxFlow += flow[i][t];
  84.  
  85.     printf("%d\n", maxFlow);
  86.   return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement