fork download
copy 
  1. /**
  2.  * Problem: Find the maximum flow in given graph
  3.  *
  4.  * Input:
  5.  * First line contains n and m: number of nodes and edges on graph
  6.  * From the second line to (m+1)'th line, each line contains u, v, c: an directed edge from u to v with capacity c
  7.  *
  8.  * Output:
  9.  * Only 1 line contains the maximum flow found on graph with source is vertex 1 and sink is vertex n
  10.  *
  11.  * Constraints:
  12.  * 1 <= n <= 10^5
  13.  * 1 <= m <= 10^6
  14.  * 1 <= c <= 10^9
  15.  * m <= n*(n-1)/2
  16.  * The given graph may contains both (u,v) and (v,u) with different capacities
  17.  * The given graph may contains duplicated edges (total capacity on that edge is the sum of individual capacities)
  18.  *
  19.  * Example:
  20.  * Input:
  21.  * 4 6
  22.  * 1 2 3
  23.  * 1 2 1
  24.  * 2 4 2
  25.  * 1 3 4
  26.  * 3 4 5
  27.  * 4 1 3
  28.  *
  29.  * Output:
  30.  * 6
  31.  *
  32. **/
  33.  
  34.  
  35. #include <bits/stdc++.h>
  36. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  37. using namespace std;
  38.  
  39. const int maxn = 1e5 + 10;
  40. const int MOD = 1e9 + 7;
  41. const long long MODLL = 1000000000000000011LL;
  42. // Dung luong flow toi da
  43.  
  44.  
  45. int n,m,s,t;
  46. struct EDGE{
  47.     int v, rev; //rev = chi so cua dinh u trong ma tran ke a[v]
  48.     long long capa;
  49.     long long flow;
  50. };
  51. vector<EDGE> a[maxn];
  52. // Do thi
  53.  
  54. long long excess[maxn];
  55. int height[maxn];
  56. bitset<maxn> active;
  57. vector<int> B[maxn];
  58. int cnth[maxn];
  59.  
  60. int highest;
  61.  
  62. int cnt_relabel, cnt_gap;
  63.  
  64. void activate(int u){
  65.     if (!active[u] && excess[u] > 0 && height[u] < n){
  66.         active[u] = true;
  67.         B[height[u]].push_back(u);
  68.         highest = max(highest, height[u]);
  69.     }
  70. }
  71.  
  72. void make_gap(int k){
  73.     up(u,1,n) if (height[u] >= k){
  74.         B[height[u]].clear();
  75.         --cnth[height[u]];
  76.         height[u] = n;
  77.         ++cnth[n];
  78.     }
  79.     ++cnt_gap;
  80. //    cout << "O(n)\n";
  81. }
  82.  
  83. void push(int u, int i){
  84.     EDGE& e = a[u][i];
  85.     int v = e.v;
  86.     long long delta = min(excess[u], e.capa - e.flow);
  87.  
  88.     EDGE& rev_e = a[v][e.rev];
  89.  
  90.     e.flow += delta;
  91.     rev_e.flow -= delta;
  92.     excess[u] -= delta;
  93.     excess[v] += delta;
  94.     activate(v);
  95. }
  96.  
  97. void relabel(int u){
  98.     --cnth[height[u]];
  99.     height[u] = n;
  100.     for (EDGE e : a[u]){
  101.         if (e.capa - e.flow > 0){
  102.             height[u] = min(height[u], height[e.v] + 1);
  103.         }
  104.     }
  105.     ++cnth[height[u]];
  106.     activate(u);
  107.     ++cnt_relabel;
  108. //    cout << "O(deg(u))\n";
  109. }
  110.  
  111. void discharge(int u){
  112.     for (int i = 0; i < (int)a[u].size(); i++){
  113.         EDGE e = a[u][i];
  114.         int v = e.v;
  115.         if (e.capa - e.flow > 0 && height[u] == height[v] + 1){ //excess[u] > 0
  116.             push(u, i);
  117.         }
  118.         if (excess[u] == 0) return;
  119.     }
  120.  
  121.     if (cnth[height[u]] == 1 && cnt_relabel > 50*cnt_gap){
  122.         make_gap(height[u]);
  123.     } //Heuristic: choose good approximation
  124.     else relabel(u);
  125. }
  126.  
  127. void findMincut(){
  128.     vector<pair<int, int> > min_cut;
  129.     long long sum = 0;
  130.     up(u,1,n) for (EDGE e : a[u]){
  131.         int v = e.v;
  132.         long long capa = e.capa;
  133.         if (capa > 0){
  134.             if (height[u] >= n && height[v] < n){
  135.                 min_cut.push_back(make_pair(u, v));
  136.                 sum += capa;
  137.             }
  138.         }
  139.     }
  140.  
  141. //    cout << sum << "\n";
  142. //    cout << "\n";
  143. //    for (auto x : min_cut){
  144. //        cout << x.first << " " << x.second << "\n";
  145. //    }
  146. }
  147.  
  148. void findMaxflow(){
  149.     excess[s] = MODLL;
  150.     height[s] = n;
  151.     cnth[0] = n-1;
  152.     cnth[n] = 1;
  153.  
  154.     for (int i = 0; i < (int)a[s].size(); i++){
  155.         EDGE& e = a[s][i];
  156.         if (e.capa > 0) push(s, i);
  157.     }
  158.  
  159.     while (highest >= 0){
  160.         while (!B[highest].empty()){
  161.             int u = B[highest].back();
  162.             B[highest].pop_back();
  163.             active[u] = false;
  164.             if (u == t) continue;
  165.             discharge(u);
  166.         }
  167.         --highest;
  168.     }
  169. }
  170.  
  171.  
  172.  
  173.  
  174.  
  175. //----- INPUT AND BUILD GRAPH -----
  176. map<pair<int, int>, long long> saved_edges;
  177. map<pair<int, int>, bool> added;
  178.  
  179. void buildBiGraph(){
  180.     up(i,1,m){
  181.         int u,v;
  182.         long long w;
  183.         cin >> u >> v >> w;
  184.         if (u == v) continue;
  185.         if (u > v) swap(u, v);
  186.         saved_edges[make_pair(u, v)] += w;
  187.     }
  188.  
  189.     for (auto e : saved_edges){
  190.         int u = e.first.first;
  191.         int v = e.first.second;
  192.         long long w = e.second;
  193.  
  194.         a[u].push_back({v, int(a[v].size()), w, 0});
  195.         a[v].push_back({u, int(a[u].size())-1, w, 0});
  196.     }
  197. }
  198.  
  199. void buildDiGraph(){
  200.     up(i,1,m){
  201.         int u,v;
  202.         long long w;
  203.         cin >> u >> v >> w;
  204.         if (u == v) continue;
  205.         saved_edges[make_pair(u, v)] += w;
  206.     }
  207.  
  208.     for (auto e : saved_edges){
  209.         int u = e.first.first;
  210.         int v = e.first.second;
  211.         long long w = e.second;
  212.  
  213.         if (!added[make_pair(u, v)]){
  214.             added[make_pair(u, v)] = added[make_pair(v, u)] = true;
  215.             a[u].push_back({v, int(a[v].size()), w, 0});
  216.             a[v].push_back({u, int(a[u].size())-1, saved_edges[make_pair(v, u)], 0});
  217.         }
  218.     }
  219. }
  220.  
  221. void find_flow_to_sink();
  222.  
  223. signed main(){
  224.     ios_base::sync_with_stdio(false);
  225.     cin.tie(0);
  226.     #define Task "A"
  227.     if (fopen(Task".inp", "r")){
  228.         freopen(Task".inp", "r", stdin);
  229.         freopen(Task".out", "w", stdout);
  230.     }
  231.  
  232.     cin >> n >> m;
  233.     s = 1, t = n;
  234.  
  235.     buildDiGraph(); //choose buildBiGraph() or buildDiGraph() to make graph bidirectional or not.
  236.     findMaxflow();
  237.     cout << excess[t];
  238. }
  239.  
  240.  
  241.  
  242. void find_flow_to_sink(){
  243.     long long sum2 = 0;
  244.     for (EDGE& e : a[t]){
  245.         int v = e.v;
  246.         EDGE& rev_e = a[v][e.rev];
  247.         sum2 += rev_e.flow;
  248.     }
  249.     cout << sum2;
  250. }
  251.  
  252. //Excess[t], sum(flow from v to t) with all v->t, or sum of capacity on Min-cut edges
  253. //are all max flow we need to find
  254.  
  255. //Some nodes still have excess, but that's not problem to find max flow
  256.  
Success #stdin #stdout 0.01s 9492KB
comments (?)
stdin
copy 
4 6
1 2 3
1 2 1
2 4 2
1 3 4
3 4 5
4 1 3
stdout
copy 
6
https://ideone.com/SwqQAF
Push-Relabel with HLPP Gap heuristic on 1e5 nodes, 1e6 edges. Allow directional and bidirectional graph. Choose good heuristic approximation for better execution time
language:
C++14 (gcc 8.3)
created:
40 days ago
visibility:
secret

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!