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 109 1 17 189 2 12 139 3 11 121 5 3 41 6 6 71 7 7 82 5 9 102 6 2 32 7 0 13 5 3 43 6 1 23 7 6 75 10 16 176 10 10 117 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 INF0x3f3f3f3f; const int N2e25,M2e55; 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 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); cinnmst; S0,Tn1; for(int i0; im; i) { int a,b,c,d; cinabcd; add(a,b,c,d); A[a]-c,A[b]c; } int tot0; for(int i1; in; i) { if(A[i]0) add(S,i,0,A[i]),totA[i]; else if(A[i]0) add(i,T,0,-A[i]); } add(t,s,0,INF); if(dinic()tot) { LL resf[idx-1]; Ss,Tt; f[idx-1]f[idx-2]0; coutresdinic()endl; /*for(int k1; km; k) { int i2*(k-1); coutf[i^1]low[i]endl; }*/ } else coutNo 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/161438841https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/127179286https://www.acwing.com/solution/content/123860/https://www.acwing.com/solution/content/72754/