[文章目录]
Description
幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？n<=300 m<= n(n-1)/2
网络流最小割。对于每个小朋友建一个点，源点向他连边表示碎觉，他向汇点连边，表示不碎觉。其中和小朋友意愿相反的流量为1。对于一对好朋友，我们将两个点互相连接，流量为1，当且仅当两个人的意愿相反时该边会被割掉。原图的最小割即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int head[400],to[201000],nxt[201000],f[201000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[410];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
int x; s=0; t=n+1;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
if(x) add(s,i,1);
else add(i,t,1);
}
int y;
while(m--)
{
scanf("%d%d",&x,&y);
add(x,y,1); add(y,x,1);
}
while(bfs()) ans+=dinic(s,inf);
printf("%d",ans);
return 0;
}