AcWing 2189：有源汇上下界最大流 ← Dinic算法
【题目来源】
https://www.acwing.com/problem/content/2191/
【题目描述】
给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。
给定源点 S 和汇点 T，求源点到汇点的最大流。
【输入格式】
第一行包含四个整数 n,m,S,T。
接下来 m 行，每行包含四个整数 a,b,c,d，表示点 a 和 b 之间存在一条有向边，该边的流量下界为 c，流量上界为 d。
点编号从 1 到 n。
【输出格式】
输出一个整数表示最大流。
如果无解，则输出 No Solution。
【输入样例】
10 15 9 10
9 1 17 18
9 2 12 13
9 3 11 12
1 5 3 4
1 6 6 7
1 7 7 8
2 5 9 10
2 6 2 3
2 7 0 1
3 5 3 4
3 6 1 2
3 7 6 7
5 10 16 17
6 10 10 11
7 10 14 15
【输出样例】
43
【数据范围】
1≤n≤202,
1≤m≤9999 ,
1≤a,b≤n,
0≤c≤d≤10^5
【算法分析】
Dinic算法：https://blog.csdn.net/hnjzsyjyj/article/details/161317988
【算法代码】
●A[N] —— 流量平衡差数组，记录每个点“流入 - 流出”的差值，判断是否存在可行流。
●上下界网络流代码中的边数 M 至少要 2e5，否则随机样例炸。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int N=2e2+5,M=2e5+5; int h[N],e[M],ne[M],idx,f[M],low[M]; int q[N],cur[N],d[N],A[N]; int n,m,s,t,S,T; void add(int a,int b,int c,int d) { e[idx]=b,ne[idx]=h[a],f[idx]=d-c,low[idx]=c,h[a]=idx++; e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++; } bool bfs() { memset(d,-1,sizeof d); int hh=0,tt=0; q[0]=S,d[S]=0; while(hh<=tt) { int u=q[hh++]; for(int i=h[u]; ~i; i=ne[i]) { int v=e[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(u==T) return lim; int flow=0; for(int i=cur[u]; ~i && flow<lim; i=ne[i]) { cur[u]=i; int v=e[i]; if(d[v]==d[u]+1 && f[i]) { int t=dfs(v,min(f[i],lim-flow)); if(!t) d[v]=-1; f[i]-=t,f[i^1]+=t,flow+=t; } } return flow; } LL dinic() { LL r=0,flow=0; while(bfs()) { //0~T for(int i=0; i<=T; i++) cur[i]=h[i]; while(flow=dfs(S,INF)) r+=flow; } return r; } int main() { memset(h,-1,sizeof h); cin>>n>>m>>s>>t; S=0,T=n+1; for(int i=0; i<m; i++) { int a,b,c,d; cin>>a>>b>>c>>d; add(a,b,c,d); A[a]-=c,A[b]+=c; } int tot=0; for(int i=1; i<=n; i++) { if(A[i]>0) add(S,i,0,A[i]),tot+=A[i]; else if(A[i]<0) add(i,T,0,-A[i]); } add(t,s,0,INF); if(dinic()==tot) { LL res=f[idx-1]; S=s,T=t; f[idx-1]=f[idx-2]=0; cout<<res+dinic()<<endl; /*for(int k=1; k<=m; k++) { int i=2*(k-1); cout<<f[i^1]+low[i]<<endl; }*/ } else cout<<"No Solution\n"; return 0; } /* in: 10 15 9 10 9 1 17 18 9 2 12 13 9 3 11 12 1 5 3 4 1 6 6 7 1 7 7 8 2 5 9 10 2 6 2 3 2 7 0 1 3 5 3 4 3 6 1 2 3 7 6 7 5 10 16 17 6 10 10 11 7 10 14 15 out: 43 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/161438841
https://blog.csdn.net/hnjzsyjyj/article/details/161317988
https://blog.csdn.net/hnjzsyjyj/article/details/127179286
https://www.acwing.com/solution/content/123860/
https://www.acwing.com/solution/content/72754/