AcWing 2234：多源汇最大流 ← Dinic算法

【题目来源】https://www.acwing.com/problem/content/2236/【题目描述】给定一个包含 n 个点 m 条边的有向图并给定每条边的容量边的容量非负。其中有 Sc 个源点Tc 个汇点。图中可能存在重边和自环。求整个网络的最大流。【输入格式】第一行包含四个整数 n,m,Sc,Tc。第二行包含 Sc 个整数表示所有源点的编号。第三行包含 Tc 个整数表示所有汇点的编号。接下来 m 行每行三个整数 u,v,c表示从点 u 到点 v 存在一条有向边容量为 c。点的编号从 1 到 n。​​​​​​​【输出格式】输出一个整数表示整个网络的最大流。​​​​​​​【输入样例】4 5 2 22 41 34 2 304 3 202 3 202 1 301 3 40【输出样例】70【数据范围】2≤n≤10000,1≤m≤10^5,0≤c≤10000,保证源点集合和汇点集合没有交集。​​​​​​​【算法分析】● 快读函数https://blog.csdn.net/hnjzsyjyj/article/details/120131534int read() { //fast read int x0,f1; char cgetchar(); while(c0 || c9) { //!isdigit(c) if(c-) f-1; cgetchar(); } while(c0 c9) { //isdigit(c) xx*10c-0; cgetchar(); } return x*f; }● Dinic 算法https://blog.csdn.net/hnjzsyjyj/article/details/161317988【算法代码一】网络流的 Dinic 算法代码中表示边数的常量 M 通常取题设条件边数的 4 倍可防止 TLE。#include bits/stdc.h using namespace std; typedef long long LL; const int N1e45,M4e55; const int INF0x3f3f3f3f; int n,m,S,T; int h[N],e[M],ne[M],f[M],idx; int d[N],cur[N],q[N]; void add(int a,int b,int c) { f[idx]c,e[idx]b,ne[idx]h[a],h[a]idx; f[idx]0,e[idx]a,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { //0~T for(int i0; iT; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } int main() { memset(h,-1,sizeof h); int sc,tc,s,t; cinnmsctc; S0,Tn1; while(sc--) cins,add(S,s,INF); while(tc--) cint,add(t,T,INF); while(m--) { int a,b,c; cinabc; add(a,b,c); } coutdinic()endl; return 0; } /* in: 4 5 2 2 2 4 1 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40 out: 70 */【算法代码二快读Dinic算法】实践证明本题不用快读只需如在算法代码一中把表示边数的常量 M 取为题设条件边数的 4 倍即可防止 TLE。#include bits/stdc.h using namespace std; typedef long long LL; const int N1e45,M4e55; const int INF0x3f3f3f3f; int n,m,S,T; int h[N],e[M],ne[M],f[M],idx; int d[N],cur[N],q[N]; int read() { //fast read int x0,f1; char cgetchar(); while(c0 || c9) { //!isdigit(c) if(c-) f-1; cgetchar(); } while(c0 c9) { //isdigit(c) xx*10c-0; cgetchar(); } return x*f; } void add(int a,int b,int c) { f[idx]c,e[idx]b,ne[idx]h[a],h[a]idx; f[idx]0,e[idx]a,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { //0~T for(int i0; iT; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } int main() { memset(h,-1,sizeof h); int sc,tc,s,t; nread(),mread(),scread(),tcread(); S0,Tn1; while(sc--) sread(),add(S,s,INF); while(tc--) tread(),add(t,T,INF); while(m--) { int a,b,c; aread(),bread(),cread(); add(a,b,c); } coutdinic()endl; return 0; } /* in: 4 5 2 2 2 4 1 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40 out: 70 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/161438841https://blog.csdn.net/hnjzsyjyj/article/details/161441409https://blog.csdn.net/hnjzsyjyj/article/details/161446211