fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 2e5+5;
  11.  
  12. int n, m;
  13.  
  14. struct FlowEdge {
  15.     int v, u;
  16.     long long cap, flow = 0;
  17.     FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
  18. };
  19.  
  20. struct Dinic {
  21.     const long long flow_inf = 1e18;
  22.     vector<FlowEdge> edges;
  23.     vector<vector<int>> adj;
  24.     int n, m = 0;
  25.     int s, t;
  26.     vector<int> level, ptr;
  27.     queue<int> q;
  28.  
  29.     Dinic(int n, int s, int t) : n(n), s(s), t(t) {
  30.         adj.resize(n);
  31.         level.resize(n);
  32.         ptr.resize(n);
  33.     }
  34.  
  35.     void add_edge(int v, int u, long long cap) {
  36.         edges.emplace_back(v, u, cap);
  37.         edges.emplace_back(u, v, 0);
  38.         adj[v].push_back(m);
  39.         adj[u].push_back(m + 1);
  40.         m += 2;
  41.     }
  42.  
  43.     bool bfs() {
  44.         while (!q.empty()) {
  45.             int v = q.front();
  46.             q.pop();
  47.             for (int id : adj[v]) {
  48.                 if (edges[id].cap == edges[id].flow)
  49.                     continue;
  50.                 if (level[edges[id].u] != -1)
  51.                     continue;
  52.                 level[edges[id].u] = level[v] + 1;
  53.                 q.push(edges[id].u);
  54.             }
  55.         }
  56.         return level[t] != -1;
  57.     }
  58.  
  59.     long long dfs(int v, long long pushed) {
  60.         if (pushed == 0)
  61.             return 0;
  62.         if (v == t)
  63.             return pushed;
  64.         for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
  65.             int id = adj[v][cid];
  66.             int u = edges[id].u;
  67.             if (level[v] + 1 != level[u])
  68.                 continue;
  69.             long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
  70.             if (tr == 0)
  71.                 continue;
  72.             edges[id].flow += tr;
  73.             edges[id ^ 1].flow -= tr;
  74.             return tr;
  75.         }
  76.         return 0;
  77.     }
  78.  
  79.     long long flow() {
  80.         long long f = 0;
  81.         while (true) {
  82.             fill(level.begin(), level.end(), -1);
  83.             level[s] = 0;
  84.             q.push(s);
  85.             if (!bfs())
  86.                 break;
  87.             fill(ptr.begin(), ptr.end(), 0);
  88.             while (long long pushed = dfs(s, flow_inf)) {
  89.                 f += pushed;
  90.             }
  91.         }
  92.         return f;
  93.     }
  94. };
  95. void solve()
  96. {
  97.  
  98. }
  99.  
  100. int32_t main()
  101. {
  102. 	ios_base::sync_with_stdio(0); cin.tie(0);
  103. 	cin>>n>>m;
  104. 	Dinic ezskip(n, 0, n-1);
  105. 	for(int i=1; i<=m; i+=1)
  106. 	{
  107. 		int x,y,w; cin>>x>>y>>w;
  108. 		// cout<<x-1<<" "<<y-1<<" "<<w<<'\n';
  109. 		ezskip.add_edge(x-1, y-1, w);
  110. 	}
  111. 	cout<<ezskip.flow()<<'\n';
  112. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin 
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3
stdout 
3
https://ideone.com/HZWZm1
language:
C++14 (gcc 8.3)
created:
5 days 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!