fork(2) download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Dinic's 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 dest, flow, sec;
  15.   edge(int _dest, int _flow, int _sec) : dest(_dest), flow(_flow), sec(_sec) {}
  16. };
  17.  
  18. std::vector<edge> edges[MAXN];
  19. int d[MAXN], n, m;
  20.  
  21. bool bfs(int s, int t) {
  22.   std::queue<int> queue;
  23.   queue.push(s);
  24.   std::fill(d, d + n, 0);
  25.   d[s] = 1;
  26.   while (!queue.empty()) {
  27.     int v = queue.front();
  28.     queue.pop();
  29.     for (int i = 0; i < (int) edges[v].size(); ++i) {
  30.       if (!d[edges[v][i].dest] && edges[v][i].flow > 0) {
  31.         d[edges[v][i].dest] = d[v] + 1;
  32.         queue.push(edges[v][i].dest);
  33.       }
  34.     }
  35.   }
  36.   return d[t]; 
  37. }
  38.  
  39. int dfs(int v, int t, int min_c) {
  40.   if (v == t) {
  41.     return min_c;
  42.   }
  43.   int res = 0;
  44.   for (int i = 0; i < (int) edges[v].size(); ++i) {
  45.     if (d[edges[v][i].dest] == d[v] + 1 && edges[v][i].flow > 0) {
  46.       int y = dfs(edges[v][i].dest, t, std::min(min_c, edges[v][i].flow));
  47.       res += y;
  48.       edges[v][i].flow -= y;
  49.       edges[edges[v][i].dest][edges[v][i].sec].flow += y;
  50.       min_c -= y;
  51.       if (min_c == 0) {
  52.         break;
  53.       }
  54.     }
  55.   }
  56.   return res;
  57. }
  58.  
  59. int maxflow(int s, int t) {
  60.   int res = 0;
  61.   while (bfs(s, t)) {
  62.     res += dfs(s, t, INF);
  63.   }
  64.   return res;
  65. }
  66.  
  67. int main() {
  68.   int a, b, c;
  69.   scanf("%d %d", &n, &m);
  70.   for (int i = 0; i < m; ++i) {
  71.     scanf("%d %d %d", &a, &b, &c);
  72.     --a, --b;
  73.     edges[a].push_back(edge(b, c, edges[b].size()));
  74.     edges[b].push_back(edge(a, 0, edges[a].size() - 1));
  75.   }
  76.   int s, t;
  77.   scanf("%d %d", &s, &t);
  78.   printf("%d\n", maxflow(s - 1, t - 1));
  79.   return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 2976KB
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/IRvLl
Dinic
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!