[文章目录]
Description
新浪体育最近在吉林教育学院进行了一次大规模的调查，调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者，大家齐聚一堂，各抒己见。每一位参与者都将发言，阐述自己的看法。参与者的心里都有一个看法，比如FireDancer认为切尔西不可能夺冠，而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友，所以可能FireDancer为了迁就自己的好朋友，会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网，希望你能安排每个人的发言内容，使得违心说话的人的总数与发言时立场不同的朋友（对）的总数的和最小。n<=300 m<=n(n-1)/2
网络流最小割。s向每个人连边，表示该人并不认为可以赢，每个人向t连边，表示该人认为可以赢，对于和真实想法相反的边流量设为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;
}