本文共 2298 字，大约阅读时间需要 7 分钟。

$思想是,如果存在可行流,每条边必定至少有下界的流量$

$那么直接用下届填充边的流量$

$每条边的流量就变成了[0,up-down]$

$此时有一些点流入的流量大于流出的流量,记作in[i]<0$

$有一些点流入的流量小于流出的流量,记作in[i]>0$

$对于in[i]<0的点,流入太多,那么给汇点t$

$对于in[i]>0的点,流出太多,那么源点s提供给它$

$这样一来,在新图上跑最大流,最大流会填充in[i]等于0$

$这样就得到一个可行流,边的流量是下界+反向边的流量$

#include 
   
    using namespace std;const int maxn=2e5+10;const int inf=1e9;struct edge{	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){	d[++cnt]=(edge){v,head[u],flow},head[u]=cnt;	d[++cnt]=(edge){u,head[v],0},head[v]=cnt;}int n,m,s,t;int in[maxn],dis[maxn],up[maxn],down[maxn];bool bfs(){	for(int i=s;i<=t;i++)	dis[i]=0;	dis[s]=1; queue
    
     q; q.push( s );	while( !q.empty() )	{		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{			int v=d[i].to;			if( dis[v]==0&&d[i].flow )			{				dis[v]=dis[u]+1;				if( v==t )	return true;				q.push( v );			}		}	}	return false;}int dinic(int u,int flow){	if( u==t )	return flow;	int res=flow;	for(int i=head[u];i&&res;i=d[i].nxt )	{		int v=d[i].to;		if( dis[v]==dis[u]+1&&d[i].flow )		{			int temp=dinic(v,min(d[i].flow,res) );			if( temp==0 )	dis[v]=0;			d[i].flow-=temp,d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}int main(){	cin >> n >> m;	for(int i=1;i<=m;i++)	{		int l,r; cin >> l >> r >> down[i] >> up[i];		add(l,r,up[i]-down[i] );		in[l]-=down[i],in[r]+=down[i];		//这条边有down[i]的流量,所以前面l需要down[i]流入,r需要流出down[i] 	}	s=0,t=n+1;	int ans=0,sumn=0;	for(int i=1;i<=n;i++)		if( in[i]<0 )	add(i,t,-in[i] );//流入太多,给汇点 		else	add(s,i,in[i] ),sumn+=in[i];//流出太多,源点补充 	while( bfs() )	ans+=dinic(s,inf);	puts( ans==sumn?"YES":"NO");	if( ans!=sumn )	return 0;	for(int i=2; i<=m*2+1; i+=2)		cout << d[i^1].flow+down[i/2] << '\n';}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108237527 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！