[bzoj]1934: [Shoi2007]Vote 善意的投票

原题链接: 善意的投票

题目大意：
选定每个人投的票的种类，使冲突最少。冲突数定义为：边的两端票种不一样的边数+违背自己意愿的个数。
理解题意：
可以把每个人都看成点。

• 若他想投同意票，则从源点向他连边。
• 若他想投反对票，则从他向汇点连边。
• 朋友之间，连正反流量都为1的双向边。

那么我们的目标就是把这么多人分成两个不同的集合（一个同意一个反对）。我们可以发现，如果我们记两个点之间有流量为这两个人投相同的票。可以发现，把这么多人分成两个集合的代价就是这个图的最小割（理解下）。

那么就是最大流==最小割，模板套上去就行了。

下面是代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int M=200000,N=309,inf=(1<<31)-1;
int n,m,ver[M],head[N],next[M],edge[M],x,y,f,cnt=1,d[N],s,t;
int maxflow=0,flow;
queue  q;
void add(int x,int y,int a);
bool bfs();
int dinic(int x,int flow);
int main()
{
	//freopen("data.in","r",stdin);
	cin>>n>>m;
	s=0,t=n+1;
	for(int i=1;i<=n;i++){
		cin>>f;
		if(f)add(s,i,1),add(i,s,0);
		else add(i,t,1),add(t,i,0);

	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		add(x,y,1);
		add(y,x,1);
	}
	while(bfs()){
		while((flow=dinic(s,inf))){maxflow+=flow;}
	}
	cout<