跳到主要内容

拓展上下界网络流

· 阅读需 7 分钟

1.无源汇上下界可行流​

我们将所有连入点的边的流量下界统计起来，作为其入流

然后再将连出点 的边的流量下界统计起来，作为其出流

我们知道一个图上只有源点与汇点不满足流量守恒，所以只要设法把点的入流和出流差消掉就可以了

都说到这里了，是不是很显然的就能发现将多出来的流推给源点和汇点就可以了

所以我们的思路也很明确了：

<1>虚拟源点与汇点

<2>在原图上连边，边的流量设为流量上界减去流量下界

<3>统计每个点的入流与出流，如果入流大于出流，那么从源点向这个点连边，反之从这个点向汇点连边，流量即为入流与出流的差

<4>从虚拟源点向虚拟汇点跑最大流，如果流能跑满，即从源点出发没有一条有剩余流量的边，说明有可行流，反之则没有

#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e2+10, M=1.1e4+10;
const ll inf=1e18;

int head[N], ver[M<<1], nxt[M<<1], now[N], CNT=1;
ll edge[M<<1];
void add( int u,int v,int w )
{
	ver[++CNT]=v, edge[CNT]=w, nxt[CNT]=head[u], head[u]=CNT;
	ver[++CNT]=u, edge[CNT]=0, nxt[CNT]=head[v], head[v]=CNT;
} 

int n, m, s, t;
int d[N], upper[M], lower[M];
ll w[N];

inline void intt()
{
	for( int i=1;i<=n+2;i++ ) d[i]=0;
}

inline bool bfs()
{
	intt();
	queue< int > q;
	q.push( s ), d[s]=1;
	now[s]=head[s];
	while( !q.empty() )
	{
		auto x=q.front();
		q.pop();
		for( int i=head[x];i;i=nxt[i] ) if( edge[i] && !d[ver[i]] )
		{
			d[ver[i]]=d[x]+1;
			now[ver[i]]=head[ver[i]];
			if( ver[i] == t ) QAQ true;
			q.push( ver[i] );
		}
	}
	
	QAQ false;
}

inline ll dinic( int x,ll flow )
{
	if( x == t ) return flow;
	ll rest=flow;
	for( int i=now[x];i && rest;i=nxt[i] )
	{
		now[x]=i;
		if( edge[i] && d[ver[i]] == d[x]+1 )
		{
			ll sonflow=dinic( ver[i],min( rest,edge[i] ) );
			if( !sonflow ) d[ver[i]]=0;
			edge[i]-=sonflow;
			edge[i^1]+=sonflow;
			rest-=sonflow;
		}
	}
	QAQ flow-=rest;
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	cin>>n>>m;
	s=n+1, t=n+2;
	for( int i=1, u, v;i<=m;i++ )
	{
		cin>>u>>v>>lower[i]>>upper[i];
		add( u,v,upper[i]-lower[i] );
		w[u]+=lower[i], w[v]-=lower[i];
	}
	ll sum=0;
	for( int i=1;i<=n;i++ )
	{
		if( w[i] > 0 ) add( i,t,w[i] ), sum+=w[i];
		if( w[i] < 0 ) add( s,i,-w[i] );
	}
	ll maxflow=0, flow;
	while( bfs() ) while( flow=dinic( s,inf ) ) maxflow+=flow;
	if( maxflow != sum ){ cout<<"NO"; QWQ }
	cout<<"YES\n";
	for( int i=1;i<=m;i++ ) cout<<lower[i]+edge[i<<1|1]<<"\n";
	QWQ	 
}

2.有源汇上下界最大流​

上文说到源点和汇点不满足流量守恒，但是如果我们稍微想想就能发现：从源点流出的流与到汇点汇入的流是相等的

我们发现，现在如果将汇点与源点之间连一条容量为+∞+\infty的边，那么这个问题不就已经转化为上面我们讨论过的问题了么

现在考虑如何能使流最大

首先，与虚拟源点相连的边的剩余流量都已经空了，所以我们要想再找出一条增广路，从虚拟的源点与汇点上做文章是不行了

诶，原来的图是不是还能跑出来增广路啊！

我们将连接原来的汇点与源点的那条容量为+∞+\infty的边去掉，然后在原来的图上跑增广路，如果能跑出流量，可以验证，这流量一定是合法的，我们只需要加上即可

综上，我们的思路是：

连接源点与汇点，按照无源汇上下界可行流的操作来一遍，设此时的可行流为maxflow1maxflow1

断开连接的边，在原图上跑增广路，此时跑出的流量为maxflow2maxflow2

得到答案：maxflow1+maxflow2maxflow1+maxflow2

#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e2+10, M=1e4+10;
const ll inf=1e18;

int head[N], ver[N+M<<1], nxt[N+M<<1], now[N], CNT=1;
ll edge[N+M<<1];
void add( int u,int v,int w )
{
	ver[++CNT]=v, edge[CNT]=w, nxt[CNT]=head[u], head[u]=CNT;
	ver[++CNT]=u, edge[CNT]=0, nxt[CNT]=head[v], head[v]=CNT;
} 

int n, m, s, t;
int d[N];
ll w[N];

inline void intt()
{
	for( int i=1;i<=n+2;i++ ) d[i]=0;
}

inline bool bfs()
{
	intt();
	queue< int > q;
	q.push( s ), d[s]=1;
	now[s]=head[s];
	while( !q.empty() )
	{
		auto x=q.front();
		q.pop();
		for( int i=head[x];i;i=nxt[i] ) if( edge[i] && !d[ver[i]] )
		{
			d[ver[i]]=d[x]+1;
			now[ver[i]]=head[ver[i]];
			if( ver[i] == t ) QAQ true;
			q.push( ver[i] );
		}
	}
	
	QAQ false;
}

inline ll dinic( int x,ll flow )
{
	if( x == t ) return flow;
	ll rest=flow;
	for( int i=now[x];i && rest;i=nxt[i] )
	{
		now[x]=i;
		if( edge[i] && d[ver[i]] == d[x]+1 )
		{
			ll sonflow=dinic( ver[i],min( rest,edge[i] ) );
			if( !sonflow ) d[ver[i]]=0;
			edge[i]-=sonflow;
			edge[i^1]+=sonflow;
			rest-=sonflow;
		}
	}
	QAQ flow-=rest;
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int S, T;
	cin>>n>>m>>S>>T;
	s=n+1, t=n+2;
	for( int i=1, u, v, lower, upper;i<=m;i++ )
	{
		cin>>u>>v>>lower>>upper;
		add( u,v,upper-lower );
		w[u]+=lower, w[v]-=lower;
	}
	ll sum=0;
	for( int i=1;i<=n;i++ )
	{
		if( w[i] > 0 ) add( i,t,w[i] ), sum+=w[i];
		if( w[i] < 0 ) add( s,i,-w[i] );
	}
	add( T,S,-inf );
	ll maxflow=0, flow;
	while( bfs() ) while( flow=dinic( s,inf ) ) maxflow+=flow;
	if( maxflow != sum ){ cout<<"please go home to sleep"; QWQ }
	s=S, t=T;
	ll ans=edge[CNT];
	edge[CNT]=edge[CNT-1]=0;
	maxflow=0;
	while( bfs() ) while( flow=dinic( s,inf ) ) maxflow+=flow;
	cout<<maxflow+ans;
	QWQ	 
}