善意的投票

题目大意： 幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。每位小朋友应该怎样投票，才能使冲突数最小？

明眼人应该能看出来是一个最小割的问题，为什么是最小割呢？

因为题目要求两个集合，所以我们建立一个超级源点，和超级汇点，然后通过最小割，使得他们在两个不同的集合。

考虑建图：
我们让S连向睡觉的，不睡觉的连向T，反过来也行。

然后小朋友之间的关系呢？

如果有两个小朋友是朋友，那么我们就在他们之间连无向边。为什么是无向边呢？因为割掉一条边，就相当于是然边的两边的点分别属于不同的集合，所以好朋友之间，可以属于他们集合的其中一个，所以要无向边。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=610;
int n,m,s,t,h[N];
int head[N],nex[N*N],w[N*N],to[N*N],tot=1;
inline void ade(int a,int b,int c){
	w[++tot]=c; to[tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c); ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(s);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!h[to[i]]&&w[i]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(h[to[i]]==h[x]+1&&w[i]){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; f-=mi; fl+=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,0x3f3f3f3f);
	return res;
}
signed main(){
	cin>>n>>m; s=0; t=n+1;
	for(int i=1;i<=n;i++){
		int x;	cin>>x;
		if(x)	add(s,i,1);	else	add(i,t,1);
	}
	while(m--){
		int a,b;	cin>>a>>b;	add(a,b,1);	add(b,a,1);
	}
	cout<<dinic()<<endl;
	return 0;
}