原题链接: 善意的投票
题目大意：
选定每个人投的票的种类，使冲突最少。冲突数定义为：边的两端票种不一样的边数+违背自己意愿的个数。
理解题意：
可以把每个人都看成点。
- 若他想投同意票，则从源点向他连边。
- 若他想投反对票，则从他向汇点连边。
- 朋友之间，连正反流量都为1的双向边。
那么我们的目标就是把这么多人分成两个不同的集合（一个同意一个反对）。我们可以发现，如果我们记两个点之间有流量为这两个人投相同的票。可以发现，把这么多人分成两个集合的代价就是这个图的最小割（理解下）。
那么就是最大流==最小割，模板套上去就行了。
下面是代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
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 <int> 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<<maxflow<<endl;
return 0;
}
bool bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=next[i]){
if(edge[i]&&!d[ver[i]]){
q.push(ver[i]);
d[ver[i]]=d[x]+1;
if(ver[i]==t)return 1;
}
}
}
return 0;
}
void add(int x,int y,int a){
ver[++cnt]=y;edge[cnt]=a;next[cnt]=head[x];head[x]=cnt;
}
int dinic(int x,int flow){
if(x==t)return flow;
int res=flow,k;
for(int i=head[x];i&&res;i=next[i]){
if(edge[i]&&d[ver[i]]==d[x]+1){
k=dinic(ver[i],min(flow,edge[i]));
if(!k)d[ver[i]]=0;
edge[i]-=k;
edge[1^i]+=k;
res-=k;
}
}
return flow-res;
}