题目大意
给定一个无源无汇的网络，边的容量有上下界限制，试构造一个合理的流量。
题目分析
求无源汇上下界的可行流模板题。
①增加一个附加源和汇\(S,T\)。
②把每个节点的\(\sum b_{u,i}\)和\(\sum b_{i,v}\)求出来，\(b\)是指下界。
③对于每个节点，若\(\sum b_{u,i}-\sum b_{i,v}>0\)，则添一条从\(S\)到\(i\)，容量为\(\sum b_{u,i}-\sum b_{i,v}\)的边。
若\(\sum b_{u,i}-\sum b_{i,v}<0\)，则添一条从\(i\)到\(T\)，容量为\(\sum b_{i,v}-\sum b_{u,i}\)的边。
④对于原网络中的点，连一条容量为 up-down 的边。
⑤求从\(S\)到\(T\)的最大流，若所有与\(S\)相连的边或与\(T\)相连的边都满载，则这是一个可行解，方案为④中所连边的剩余流量+\(b\)。
代码实现
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=205*205;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n,m,S,T,num;
struct node{int next,to,pair,flow;}g[N<<1];
int h[N],cnt;
void AddEdge(int x,int y,int z){g[++cnt].to=y,g[cnt].next=h[x],h[x]=cnt,g[cnt].flow=z,g[cnt].pair=cnt+1;g[++cnt].to=x,g[cnt].next=h[y],h[y]=cnt,g[cnt].flow=0,g[cnt].pair=cnt-1;
}
int GAP[N],dis[N];
void Init(){static int q[N];int l=0,r=1;q[++l]=T,++GAP[dis[T]=1];while(l<=r){int x=q[l++];for(int i=h[x];i;i=g[i].next){int to=g[i].to;if(!dis[to])++GAP[dis[to]=dis[x]+1],q[++r]=to; }}
}
int Dfs(int x,int Maxf){if(x==T||!Maxf)return Maxf;int ret=0;for(int i=h[x];i;i=g[i].next){int to=g[i].to;if(g[i].flow&&dis[x]==dis[to]+1){int dlt=Dfs(to,min(g[i].flow,Maxf-ret));g[i].flow-=dlt;g[g[i].pair].flow+=dlt;ret+=dlt;if(dis[S]==num+1||ret==Maxf)return ret;}}if(!(--GAP[dis[x]]))dis[S]=num+1;else GAP[++dis[x]]++;return ret;
}
int SAP(){Init();int ans=Dfs(S,MAXN);while(dis[S]<=num)ans+=Dfs(S,MAXN);return ans;
}
struct Edge{int x,y,b,c;}s[N];
int inb[N],otb[N];
int main(){n=Getint(),m=Getint(),S=0,T=n+m+1,num=T+1;for(int i=1;i<=m;i++){s[i].x=Getint(),s[i].y=Getint(),s[i].b=Getint(),s[i].c=Getint();AddEdge(s[i].x,s[i].y,s[i].c-s[i].b);inb[s[i].y]+=s[i].b,otb[s[i].x]+=s[i].b;}for(int i=1;i<=n;i++)if(inb[i]>otb[i])AddEdge(S,i,inb[i]-otb[i]);else AddEdge(i,T,otb[i]-inb[i]);SAP();bool flag=0;for(int i=h[S];i;i=g[i].next)flag|=(g[i].flow>0);cout<<((flag)?"NO":"YES");return 0;
}