AcWing 2188：无源汇上下界可行流 ← Dinic算法

【题目来源】https://www.acwing.com/problem/content/2190/【题目描述】给定一个包含 n 个点 m 条边的有向图每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下所有边满足流量限制。【输入格式】第一行包含两个整数 n 和 m。接下来 m 行每行包含四个整数 a,b,c,d 表示点 a 和 b 之间存在一条有向边该边的流量下界为 c流量上界为 d。点编号从 1 到 n。【输出格式】如果存在可行方案则第一行输出 YES接下来 m 行每行输出一个整数其中第 i 行的整数表示输入的第 i 条边的流量。如果不存在可行方案直接输出一行 NO。如果可行方案不唯一则输出任意一种方案即可。【输入样例一】4 61 2 1 32 3 1 33 4 1 34 1 1 31 3 1 34 2 1 3【输出样例一】YES123211【输入样例二】4 61 2 1 22 3 1 23 4 1 24 1 1 21 3 1 24 2 1 2【输出样例二】NO【数据范围】1≤n≤200,1≤m≤10200,1≤a,b≤n,0≤c≤d≤10000【算法分析】Dinic算法https://blog.csdn.net/hnjzsyjyj/article/details/161317988【算法代码】A[N] —— 流量平衡差数组记录每个点“流入 - 流出”的差值判断是否存在可行流。#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; 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); cinnm; S0,Tn1; for(int i1; 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]); } if(dinic()tot) { coutYES\n; for(int k1; km; k) { int i2*(k-1); coutf[i^1]low[i]endl; } } else coutNO\n; return 0; } /* in: 4 6 1 2 1 3 2 3 1 3 3 4 1 3 4 1 1 3 1 3 1 3 4 2 1 3 out: YES 1 2 3 2 1 1 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://blog.csdn.net/hnjzsyjyj/article/details/127179286https://www.acwing.com/solution/content/61022/