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

$这只是其中一种做法$(我暂时还没有理解,只是先放个模板而已)

$首先还是根据下界来建图,原图源点s,汇点t$

$然后因为流量守恒,新建超级源s1和超级汇t1向各个点连边$

$跑一遍s1到t1的最大流(也就是可行流)$

$然后t到s连一条流量inf的边$

$再跑一遍s1到t1的最大流$

$此时t到s的那条边的反向弧流量就是最小流$

#include 
   
    using namespace std;const int maxn=2e5+10;const int inf=1e9;int n,m,s,t;struct edge{	int to,flow,nxt;}d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int flow){	d[++cnt]=(edge){v,flow,head[u]},head[u]=cnt;	d[++cnt]=(edge){u,0,head[v]},head[v]=cnt;}int dis[maxn],in[maxn],up[maxn],down[maxn],g[maxn];bool bfs(int s,int t){	memset(dis,0,sizeof(dis));	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 t,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,t,min(res,d[i].flow) );			if( temp==0 )	dis[v]=0;			d[i].flow-=temp,d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}int maxflow(int s,int t){	int ans=0;	while( bfs(s,t) )	ans+=dinic(s,t,inf);	return ans;}int vis[109][109],row[109],col[109];int main(){	int k;	cin >> n >> m >> k;	for(int i=1;i<=n;i++)	cin >> row[i];	for(int j=1;j<=m;j++)	cin >> col[j]; 	while( k-- )	{		int l,r; cin >> l >> r;		vis[l][r]=1;	}	int s=0,t=n+m+1;	int s1=t+1,t1=t+2;	for(int i=1;i<=n;i++)	{		int temp=0;		for(int j=1;j<=m;j++)		{			if( vis[i][j] )	continue;			//第i行向第j列连边			add(i,j+n,1); temp++; 		}		//下界是row[i],上界是temp 		add(s,i,temp-row[i]);		in[s]-=row[i],in[i]+=row[i];	}	for(int i=1;i<=m;i++)	{		int temp=0;		for(int j=1;j<=n;j++)			if( !vis[j][i] )	temp++;		add(i+n,t,temp-col[i]);		in[i+n]-=col[i],in[t]+=col[i];	}	int sumn=0;	for(int i=0;i<=n+m+1;i++)		if( in[i]>0 )	add(s1,i,in[i] ),sumn+=in[i];		else	add( i,t1,-in[i] );	int ans=maxflow(s1,t1);	add(t,s,inf);	int now=maxflow(s1,t1);	cout << d[cnt].flow;}
    
   

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