Editorial for Luồng cực đại trên mạng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int oo = 1 << 29; struct edge { int x, y, cap, flow; }; struct Flow { int n, S, T; vector < vector <int> > a; vector <int> cur, d; vector <edge> e; Flow() {} Flow(int _n, int _S, int _T) { n = _n; S = _S; T = _T; a = vector < vector <int> >(n + 1); cur = vector <int>(n + 1); d = vector <int>(n + 1); } void addEdge(int x, int y, int _cap) { edge e1 = {x, y, _cap, 0}; edge e2 = {y, x, 0, 0}; a[x].push_back(e.size()); e.push_back(e1); a[y].push_back(e.size()); e.push_back(e2); } int bfs() { queue <int> q; for (int i = 1; i <= n; i++) d[i] = -1; q.push(S); d[S] = 0; while (!q.empty() && d[T] < 0) { int x = q.front(); q.pop(); for (int i = 0; i < int(a[x].size()); i++) { int id = a[x][i], y = e[id].y; if (d[y] < 0 && e[id].flow < e[id].cap) q.push(y), d[y] = d[x] + 1; } } return d[T] >= 0; } int dfs(int x, int val) { if (!val) return 0; if (x == T) return val; for (; cur[x] < int(a[x].size()); cur[x]++) { int id = a[x][cur[x]], y = e[id].y; if (d[y] != d[x] + 1) continue; int pushed = dfs(y, min(val, e[id].cap - e[id].flow)); if (pushed) { e[id].flow += pushed; e[id ^ 1].flow -= pushed; return pushed; } } return 0; } int maxFlow() { int res = 0; while (bfs()) { for (int i = 1; i <= n; i++) cur[i] = 0; while (1) { int val = dfs(S, oo); if (!val) break; res += val; } } return res; } }; int main() { int n, m, S, T, x, y, z; cin >> n >> m >> S >> T; Flow u(n, S, T); while (m--) { scanf("%d%d%d", &x, &y, &z); u.addEdge(x, y, z); } cout << u.maxFlow() << endl; }
Code mẫu của happyboy99x
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct Edge { int from, to, cap, flow, index; Edge(int from, int to, int cap, int flow, int index) : from(from), to(to), cap(cap), flow(flow), index(index) {} }; struct PushRelabel { int N; vector<vector<Edge> > G; vector<LL> excess; vector<int> dist, active, count; queue<int> Q; PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {} void AddEdge(int from, int to, int cap) { G[from].push_back(Edge(from, to, cap, 0, G[to].size())); if (from == to) G[from].back().index++; G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1)); } void Enqueue(int v) { if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } } void Push(Edge &e) { int amt = int(min(excess[e.from], LL(e.cap - e.flow))); if (dist[e.from] <= dist[e.to] || amt == 0) return; e.flow += amt; G[e.to][e.index].flow -= amt; excess[e.to] += amt; excess[e.from] -= amt; Enqueue(e.to); } void Gap(int k) { for (int v = 0; v < N; v++) { if (dist[v] < k) continue; count[dist[v]]--; dist[v] = max(dist[v], N+1); count[dist[v]]++; Enqueue(v); } } void Relabel(int v) { count[dist[v]]--; dist[v] = 2*N; for (int i = 0; i < G[v].size(); i++) if (G[v][i].cap - G[v][i].flow > 0) dist[v] = min(dist[v], dist[G[v][i].to] + 1); count[dist[v]]++; Enqueue(v); } void Discharge(int v) { for (int i = 0; excess[v] > 0 && i < G[v].size(); i++) Push(G[v][i]); if (excess[v] > 0) { if (count[dist[v]] == 1) Gap(dist[v]); else Relabel(v); } } LL GetMaxFlow(int s, int t) { count[0] = N-1; count[N] = 1; dist[s] = N; active[s] = active[t] = true; for (int i = 0; i < G[s].size(); i++) { excess[s] += G[s][i].cap; Push(G[s][i]); } while (!Q.empty()) { int v = Q.front(); Q.pop(); active[v] = false; Discharge(v); } LL totflow = 0; for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow; return totflow; } }; int main() { ios::sync_with_stdio(false); int n, m, s, t; cin >> n >> m >> s >> t; --s; --t; PushRelabel net (n); for(int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; --u; --v; net.AddEdge(u, v, c); } cout << net.GetMaxFlow(s, t) << '\n'; return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; struct Edge { int u, v; int capacity; int flow; }; struct Network { int n; int source, sink; vector<vector<int> > a; vector<Edge> E; vector<int> cur; vector<int> dist; Network() {} Network(int n, int s, int t) { this->n = n; source = s; sink = t; a = vector<vector<int> > (n + 1); cur = dist = vector<int> (n + 1); } void addEdge(int u, int v, int c) { a[u].push_back(E.size()); E.push_back({u, v, c, 0}); a[v].push_back(E.size()); E.push_back({v, u, 0, 0}); } bool bfs() { fill(dist.begin(), dist.end(), -1); queue<int> Q; Q.push(source); dist[source] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < a[u].size(); ++i) { int id = a[u][i], v = E[id].v; if (dist[v] < 0 && E[id].flow < E[id].capacity) { dist[v] = dist[u] + 1; Q.push(v); } } } return dist[sink] >= 0; } int dfs(int u, int flow) { if (!flow) return 0; if (u == sink) return flow; for (; cur[u] < a[u].size(); ++cur[u]) { int id = a[u][cur[u]], v = E[id].v; if (dist[v] != dist[u] + 1) continue; int delta = dfs(v, min(flow, E[id].capacity - E[id].flow)); if (delta) { E[id].flow += delta; E[id ^ 1].flow -= delta; return delta; } } return 0; } int maxFlow() { int ans = 0; while (bfs()) { fill(cur.begin(), cur.end(), 0); while (true) { int delta = dfs(source, INF); if (!delta) break; ans += delta; } } return ans; } }; int main() { ios::sync_with_stdio(false); int n, m, s, t; cin >> n >> m >> s >> t; Network G (n, s, t); while (m--) { int u, v, c; cin >> u >> v >> c; G.addEdge(u, v, c); } cout << G.maxFlow() << endl; return 0; }
Code mẫu của RR
// Accepted #include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <complex> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) using namespace std; // Fastest flow struct Edge { int u, v, c, f; int next; }; struct MaxFlow { int n, s, t; vector< Edge > edges; vector<int> head, current, h, avail; vector<long long> excess; MaxFlow(int n) : n(n), head(n, -1), current(n, -1), h(n), avail(n), excess(n) { edges.clear(); } void addEdge(int u, int v, int c) { Edge xuoi = {u, v, c, 0, head[u]}; head[u] = edges.size(); edges.push_back(xuoi); Edge nguoc = {v, u, 0, 0, head[v]}; head[v] = edges.size(); edges.push_back(nguoc); } long long getFlow(int _s, int _t) { s = _s; t = _t; init(); int now = 0; queue<int> qu[2]; REP(x,n) if (x != s && x != t && excess[x] > 0) qu[now].push(x); globalLabeling(); int cnt = 0, ok = 0; while (!qu[now].empty()) { while (!qu[1-now].empty()) qu[1-now].pop(); while (!qu[now].empty()) { int x = qu[now].front(); qu[now].pop(); // DEBUG(x); while (current[x] >= 0) { int p = current[x]; if (edges[p].c > edges[p].f && h[edges[p].u] > h[edges[p].v]) { bool need = (edges[p].v != s && edges[p].v != t && !excess[edges[p].v]); push(current[x]); if (need) qu[1-now].push(edges[p].v); if (!excess[x]) break; } current[x] = edges[current[x]].next; } if (excess[x] > 0) { lift(x); current[x] = head[x]; qu[1-now].push(x); cnt++; if (cnt == n) { globalLabeling(); cnt=0; } } } now = 1 - now; } return excess[t]; } private: void init() { REP(i,n) current[i] = head[i]; int p = head[s]; while (p >= 0) { edges[p].f = edges[p].c; edges[p^1].f -= edges[p].c; excess[edges[p].v] += edges[p].c; excess[s] -= edges[p].c; p = edges[p].next; } FOR(v,0,n-1) h[v] = 1; h[s] = n; h[t] = 0; } void push(int i) { long long delta = min(excess[edges[i].u], (long long) edges[i].c - edges[i].f); edges[i].f += delta; edges[i^1].f -= delta; excess[edges[i].u] -= delta; excess[edges[i].v] += delta; } void lift(int u) { int minH = 2 * n; int p = head[u]; while (p>=0) { if (edges[p].c > edges[p].f) minH = min(minH, h[edges[p].v]); p = edges[p].next; } h[u] = minH + 1; } void globalLabeling() { REP(i,n) avail[i] = 1, h[i] = 0; h[s] = n; h[t] = 0; queue<int> q; q.push(t); avail[t] = false; while (!q.empty()) { int x = q.front(); q.pop(); int p = head[x]; while (p >= 0) { int pp = p^1; if (avail[edges[pp].u] && edges[pp].f < edges[pp].c) { h[edges[pp].u] = h[x] + 1; avail[edges[pp].u] = 0; q.push(edges[pp].u); } p = edges[p].next; } if (q.empty() && avail[s]) { avail[s] = false; q.push(s); } } REP(x,n) current[x] = head[x]; } }; int main() { ios :: sync_with_stdio(false); int n, m, s, t; cin >> n >> m >> s >> t; --s; --t; MaxFlow flow(n); while (m--) { int u, v, c; cin >> u >> v >> c; --u; --v; flow.addEdge(u, v, c); } cout << flow.getFlow(s, t) << endl; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.00001 #define oo 1111111111 #define mod 1000000007 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } // Dinic #define maxn 1011 #define maxe 1000011 struct Dinic{ int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe], last[maxn], que[maxn], level[maxn], run[maxn]; void init(int _s, int _t){ s = _s; t = _t; E = 0; memset(last, -1, sizeof(last)); } void add(int u, int v, int c1, int c2){ adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++; adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++; } bool bfs(){ memset(level, -1, sizeof(level)); level[s] = 0; int size = 0; que[size++] = s; rep(i, size){ for(int u = que[i], e = last[u]; e != -1; e = next[e]){ int v = adj[e]; if(level[v] == -1 && flow[e] < cap[e]){ level[v] = level[u] + 1; que[size++] = v; } } } return level[t] != -1; } int dfs(int u, int bot){ if(u == t) return bot; for(int &e = run[u]; e != -1; e = next[e]){ int v = adj[e], delta; if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){ flow[e] += delta; flow[e ^ 1] -= delta; return delta; } } return 0; } ll maxflow(){ ll total = 0; while(bfs()){ memcpy(run, last, sizeof(last)); for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta; } return total; } } dinic; int main(){ //OPEN(); int n, m, u, v, c; scanf("%d %d %d %d", &n, &m, &u, &v); dinic.init(u, v); rep(i, m){ scanf("%d %d %d", &u, &v, &c); dinic.add(u, v, c, 0); } printf("%d\n",dinic.maxflow()); }
Code mẫu của ll931110
{$MODE DELPHI} program NKFLOW; const input = ''; output = ''; maxn = 1000; type PNode = ^TNode; TNode = record adj: integer; link: PNode; end; var c,f: array[1..maxn,1..maxn] of integer; trace,queue: array[1..maxn] of integer; n,m,s,t: integer; a: array[1..maxn] of PNode; procedure add(u,v: integer); var P: PNode; begin New(P); P^.adj := v; P^.link := a[u]; a[u] := P; end; procedure init; var fi: text; i,u,v: integer; begin assign(fi, input); reset(fi); readln(fi, n, m, s, t); fillchar(c, sizeof(c), 0); fillchar(f, sizeof(f), 0); for i := 1 to m do begin readln(fi, u, v, c[u,v]); add(u,v); end; close(fi); end; function FindPath: boolean; var va,st,front,rear: integer; u: PNode; begin fillchar(trace, sizeof(trace), 0); front := 1; rear := 1; queue[1] := s; trace[s] := -1; repeat st := queue[front]; inc(front); u := a[st]; while u <> nil do begin va := u^.adj; if (trace[va] = 0) and (c[st,va] > f[st,va]) then begin trace[va] := st; if va = t then exit(true); inc(rear); queue[rear] := va; end; u := u^.link; end; until front > rear; FindPath := false; end; procedure IncFlow; var delta,u,v: integer; begin delta := high(longint); v := t; repeat u := trace[v]; if c[u,v] - f[u,v] < delta then delta := c[u,v] - f[u,v]; v := u; until v = s; v := t; repeat u := trace[v]; f[u,v] := f[u,v] + delta; f[v,u] := f[v,u] - delta; v := u; until v = s; end; procedure FordFulkerson; begin repeat if not FindPath then break; IncFlow; until false; end; procedure printresult; var fo: text; cost,i,j: integer; begin assign(fo, output); rewrite(fo); cost := 0; for i := 1 to n do if f[s,i] > 0 then cost := cost + f[s,i]; writeln(fo, cost); close(fo); end; begin init; FordFulkerson; printresult; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> using namespace std; struct DinicFlow { static const int INF = (int) 1e9 + 7; int numNode, numEdge; vector<int> dist, head, work; vector<int> point, flow, capa, next; DinicFlow(int n = 0) { numNode = n; numEdge = 0; dist.assign(n + 7, 0); head.assign(n + 7, -1); work.assign(n + 7, 0); } int addEdge(int u, int v, int c1, int c2 = 0) { int ret = numEdge; point.push_back(v); capa.push_back(c1); flow.push_back(0); next.push_back(head[u]); head[u] = numEdge++; point.push_back(u); capa.push_back(c2); flow.push_back(0); next.push_back(head[v]); head[v] = numEdge++; return ret; } bool bfs(int s, int t) { queue<int> q; for (int i = 1; i <= numNode; i++) dist[i] = -1; dist[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i >= 0; i = next[i]) if (flow[i] < capa[i] && dist[point[i]] < 0) { dist[point[i]] = dist[u] + 1; q.push(point[i]); } } return dist[t] >= 0; } int dfs(int s, int t, int f) { if (s == t) return f; for (int &i = work[s]; i >= 0; i = next[i]) if (flow[i] < capa[i] && dist[point[i]] == dist[s] + 1) { int d = dfs(point[i], t, min(f, capa[i] - flow[i])); if (d > 0) { flow[i] += d; flow[i ^ 1] -= d; return d; } } return 0; } int maxFlow(int s, int t) { for (int i = 1; i <= numNode; i++) flow[i] = 0; int totFlow = 0; while (bfs(s, t)) { for (int i = 1; i <= numNode; i++) work[i] = head[i]; while (true) { int d = dfs(s, t, INF); if (d == 0) break; totFlow += d; } } return totFlow; } int getFlow(int id) const { return flow[id]; } }; int main(void) { int n, m, src, snk; cin >> n >> m >> src >> snk; DinicFlow df(n); for (int love = 0; love < m; love++) { int u, v, c; cin >> u >> v >> c; df.addEdge(u, v, c); } cout << df.maxFlow(src, snk) << endl; return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; #define maxn 1010 int n, m, s, t, soluong; int a[maxn][maxn], f[maxn][maxn]; int q[maxn], la[maxn], e[maxn]; void tang() { int dt = e[t]; soluong += dt; int v = t; while(la[v]!=v) { int u = la[v]; if(u<0) { f[v][-u] -= dt; v = -u; } else { f[u][v] += dt; v = u; } } } bool bfs() { int l, r; q[l=r=0] = s; memset( la, 0, sizeof(la)); memset( e, 0, sizeof(e)); la[s] = s; e[s] = 1000000000; while(l<=r) { int u = q[l++]; for(int v=1;v<=n;++v) if(e[v]==0) { if(a[u][v]>f[u][v]) { e[v] = min( e[u], a[u][v] - f[u][v]); q[++r] = v; la[v] = u; } else if(f[v][u]>0) { e[v] = min( e[u], f[v][u]); q[++r] = v; la[v] = -u; } } if(e[t]!=0) { tang(); return true; } } return false; } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for(int i=0;i<m;++i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); a[u][v] = c; } while(bfs()); cout << soluong << endl; //system("pause"); return 0; }
Comments