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

最小割模型

$每个小朋友只有0和1两种状态$

$所以把0的小朋友连向源点,1的小朋友连向汇点$

$求s到t的最小割(最大流)就是答案$

$因为如果s到i的边被割掉,花费是1,相当于改变了i的立场到了汇点那个集合$

$如果i到t的边被割掉,同上$

$如果朋友间的边被割掉,说明其中朋友的立场是不相等的$

#include 
   
    using namespace std;const int maxn=5e5+10;const int inf=1e9;int n,m,s,t;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 dis[maxn];bool bfs(){	queue
    
     q;	for(int i=0;i<=t;i++)	dis[i]=inf;	dis[s]=0,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]==inf&&d[i].flow )			{				dis[v]=dis[u]+1;				q.push(v);				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int flow){	int res=flow;	if( u==t )	return flow;	for(int i=head[u];i;i=d[i].nxt )	{		int v=d[i].to;		if( d[i].flow&&dis[v]==dis[u]+1 )		{			int temp=dinic(v,min(res,d[i].flow) );			if( temp==0 )	dis[v]=-1;			d[i].flow-=temp;			d[i^1].flow+=temp;			res-=temp;		}		if( res==0 )	break;	}	return flow-res;}int main(){	cin >> n >> m;	t=n+1;s=0;	for(int i=1;i<=n;i++)	{		int x; cin >> x;		if( x )	add(s,i,1);		else	add(i,t,1);	}	for(int i=1;i<=m;i++)	{		int l,r;		cin >> l >> r;		add(l,r,1); add(r,l,1);	}	int ans=0;	while( bfs() )	ans+=dinic(s,inf);	cout << ans;}
    
   

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