fork(1) download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Edmonds-Karp algorithm
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <queue>
  8. #include <algorithm>
  9.  
  10. #define MAXN 10000
  11. #define INF 0x7FFFFFFF
  12.  
  13. struct edge {
  14.   int v, c, p;
  15.   edge() {}
  16.   edge(int vv, int cc, int pp) : v(vv), c(cc), p(pp) {}
  17. };
  18.  
  19. std::vector<edge> edges[MAXN];
  20. std::pair<int, int> p[MAXN];
  21. bool vis[MAXN];
  22.  
  23. int bfs(int s, int t, int n) {
  24.   std::queue<int> q;
  25.   q.push(s);
  26.   std::fill(vis, vis + n, false);
  27.   vis[s] = true;
  28.   while (!q.empty()) {
  29.     int v = q.front();
  30.     q.pop();
  31.     if (v == t) {
  32.       int min = INF;
  33.       int x = v;
  34.       while (x != s) {
  35.         min = std::min(min, edges[p[x].first][p[x].second].c);
  36.         x = p[x].first;
  37.       }
  38.       x = v;
  39.       while (x != s) {
  40.         edges[p[x].first][p[x].second].c -= min;
  41.         edges[x][edges[p[x].first][p[x].second].p].c += min;
  42.         x = p[x].first;
  43.       }
  44.       return min;
  45.     }
  46.     for (int i = 0; i < (int) edges[v].size(); ++i) {
  47.       if (!vis[edges[v][i].v] && edges[v][i].c > 0) {
  48.         vis[edges[v][i].v] = true;
  49.         q.push(edges[v][i].v);
  50.         p[edges[v][i].v] = std::make_pair(v, i);
  51.       }
  52.     }
  53.   }
  54.   return 0;
  55. }
  56.  
  57. int main() {
  58.   int n, m, a, b, c, s, t;
  59.   scanf("%d %d", &n, &m);
  60.   for (int i = 0; i < m; ++i) {
  61.     scanf("%d %d %d", &a, &b, &c);
  62.     --a, --b;
  63.     edges[a].push_back(edge(b, c, edges[b].size()));
  64.     edges[b].push_back(edge(a, 0, edges[a].size() - 1));
  65.   }
  66.   scanf("%d %d", &s, &t);
  67.   --s, --t;
  68.   int tmp, res = 0;
  69.   while (tmp = bfs(s, t, n)) {
  70.     res += tmp;
  71.   }
  72.   printf("%d\n", res);
  73.   return 0;
  74. }
  75.  
Success #stdin #stdout 0.02s 3068KB
comments (?)
stdin
copy 
6 7
1 2 5
2 3 5
3 4 5
1 6 2
6 3 2
2 5 2
5 4 2
1 4
stdout
copy 
7
https://ideone.com/IxbbL
Edmonds-karp
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!