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

文文要在$n$天内给$m$个女孩拍照

第$i$天可以给$C_i$个女孩拍照,可以给第$j$个女孩拍$[L_{,}R]张照片$

而且在第$i$天,拍照总数不能超过$D_i$

且每个女孩最少拍$g_i$张照骗

问$n$天可以最多拍多少照片

现在假设你已经模糊理解了上下界最大流再往下看吧,主要阐述一下怎么写

$为了把n天联系起来,我们需要源点s1$

$为了把m个女孩联系起来,我们需要汇点t1$

把$n$天和$m$个女孩都看成一个点

第$i$天向所有可以拍照的女孩连边,上界为$R$,下界为$L$

$s1$向每一天连边,上界是$D_i$,下届为$0$

每个女孩向$t_1$连边,上界是$inf$,下界是$g_i$

现在让每条边暂时先流过下界

这样有些点流出比较多,那么缺失的流量应该由$s_2$提供

这样有些点流入比较多,那么多余的流量应该流给$t_2$

其中$s_2,t_2$是为制造可行流虚拟的源汇点

所以先$s_2$向$t_2$跑最大流,检验是否有可行流(流量守恒)

若此时有可行流

直接从$s_1$向$t_1$跑最大流,此时最大流就是答案.

此时得到的最大流=可行流+残量网络剩余的流量

#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 main(){	while( cin >> n >> m )	{		memset(in,0,sizeof(in));		memset(head,0,sizeof(head));		cnt=1;		int s1=n+m+1,t1=n+m+2;		int s2=n+m+3,t2=n+m+4;		for(int i=1;i<=m;i++)		{			cin >> g[i];			in[t1]+=g[i],in[n+i]-=g[i];//流出加,流入减 			add(n+i,t1,inf-g[i] );		}		for(int i=1;i<=n;i++)		{			int C,D,T,L,R;			cin >> C >> D;//取材对象,每天不超过D张			add(s1,i,D);			while( C-- )			{				cin >> T >> L >> R;				T++;				in[n+T]+=L,in[i]-=L;				add(i,n+T,R-L);				} 		}		int sumn=0;		for(int i=1;i<=n+m+2;i++)			if( in[i]>0 )	add(s2,i,in[i] ),sumn+=in[i];			else	add(i,t2,-in[i]);		add(t1,s1,inf);		if( maxflow(s2,t2)!=sumn )		{			cout << -1 << '\n' << '\n';			continue;		}		cout << maxflow(s1,t1) << '\n' << '\n';	}}
    
   

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