fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define el cout << '\n'
  7.  
  8. const ll INF = 1e18;
  9.  
  10. struct Edge {
  11.     int u, v;
  12.     ll cap, flow = 0;
  13.     Edge(int u, int v, ll cap) : u(u), v(v), cap(cap) {}
  14. };
  15.  
  16. struct Dinic {
  17.     int n, s, t;
  18.     vector<Edge> edges;
  19.     vector<vector<int>> adj;
  20.     vector<int> level, ptr;
  21.  
  22.     Dinic(int n, int s, int t) : n(n), s(s), t(t) {
  23.         adj.resize(n + 1);
  24.         level.resize(n + 1);
  25.         ptr.resize(n + 1);
  26.     }
  27.  
  28.     void add_edge(int u, int v, ll cap) {
  29.         adj[u].push_back(edges.size());
  30.         edges.emplace_back(u, v, cap);
  31.         adj[v].push_back(edges.size());
  32.         edges.emplace_back(v, u, 0); // Cạnh ngược capacity = 0
  33.     }
  34.  
  35.     bool bfs() {
  36.         fill(level.begin(), level.end(), -1);
  37.         level[s] = 0;
  38.         queue<int> q;
  39.         q.push(s);
  40.         while (!q.empty()) {
  41.             int u = q.front();
  42.             q.pop();
  43.             for (int id : adj[u]) {
  44.                 if (edges[id].cap - edges[id].flow > 0 && level[edges[id].v] == -1) {
  45.                     level[edges[id].v] = level[u] + 1;
  46.                     q.push(edges[id].v);
  47.                 }
  48.             }
  49.         }
  50.         return level[t] != -1;
  51.     }
  52.  
  53.     ll dfs(int u, ll pushed) {
  54.         if (pushed == 0) return 0;
  55.         if (u == t) return pushed;
  56.         for (int &cid = ptr[u]; cid < adj[u].size(); ++cid) {
  57.             int id = adj[u][cid];
  58.             int v = edges[id].v;
  59.             if (level[v] != level[u] + 1 || edges[id].cap - edges[id].flow == 0) continue;
  60.  
  61.             ll tr = dfs(v, min(pushed, edges[id].cap - edges[id].flow));
  62.             if (tr == 0) continue;
  63.  
  64.             edges[id].flow += tr;
  65.             edges[id ^ 1].flow -= tr; // Cập nhật cạnh ngược
  66.             return tr;
  67.         }
  68.         return 0;
  69.     }
  70.  
  71.     ll max_flow() {
  72.         ll flow = 0;
  73.         while (bfs()) {
  74.             fill(ptr.begin(), ptr.end(), 0);
  75.             while (ll pushed = dfs(s, INF)) {
  76.                 flow += pushed;
  77.             }
  78.         }
  79.         return flow;
  80.     }
  81. };
  82.  
  83. int main() {
  84.     ios_base::sync_with_stdio(0); cin.tie(0);
  85.  
  86.     // Ví dụ sử dụng
  87.     int n, m, s, t;
  88.     // cin >> n >> m >> s >> t;
  89.  
  90.     // Lưu ý: Khai báo n nodes, source s, sink t
  91.     Dinic dinic(n, s, t); 
  92.  
  93.     // for(int i=0; i<m; i++) {
  94.     //     int u, v; ll c; cin >> u >> v >> c;
  95.     //     dinic.add_edge(u, v, c);
  96.     // }
  97.  
  98.     // cout << dinic.max_flow() << el;
  99.  
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v8MM19
language:
C++14 (gcc 8.3)
created:
7 hours 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!