【SHOI2007】bzoj1934 善意的投票

本文主要是介绍【SHOI2007】bzoj1934 善意的投票，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。
我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？ Input
第一行只有两个整数n，m，保证有2≤n≤300，1≤m≤n(n-1)/2。其中n代表总人数，m代表好朋友的对数。文件第二行有n个整数，第i个整数代表第i个小朋友的意愿，当它为1时表示同意睡觉，当它为0时表示反对睡觉。接下来文件还有m行，每行有两个整数i，j。表示i，j是一对好朋友，我们保证任何两对i，j不会重复。
Output 只需要输出一个整数，即可能的最小冲突数。

两派人分别向源或汇连边，朋友之间连双向边，然后求最小割。
S和T代表两个阵营，之间的割就是冲突数。另外，如果有一个人改变阵营，还要再付出一条割的代价。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int s=305,t=306,oo=0x3f3f3f3f;
int fir[310],ne[600010],to[600010],w[600010],n,m,tot,f[310],que[310];
void add(int u,int v,int x)
{tot++;ne[tot*2]=fir[u];fir[u]=tot*2;to[tot*2]=v;w[tot*2]=1;ne[tot*2+1]=fir[v];fir[v]=tot*2+1;to[tot*2+1]=u;w[tot*2+1]=x;
}
bool bfs()
{int hd,tl,u,v,i;memset(f,0,sizeof(f));que[f[s]=hd=tl=1]=s;while (hd<=tl){u=que[hd++];for (i=fir[u];i;i=ne[i])if (w[i]&&!f[v=to[i]]){f[v]=f[u]+1;que[++tl]=v;}}return f[t];
}
int dfs(int u,int lim)
{int i,v,x,ret=0;if (u==t) return lim;for (i=fir[u];i&&ret<lim;i=ne[i])if (w[i]&&f[v=to[i]]==f[u]+1){x=dfs(v,min(lim-ret,w[i]));w[i]-=x;w[i^1]+=x;ret+=x;}if (!ret) f[u]=0;return ret;
}
int main()
{int i,x,y,ans=0;scanf("%d%d",&n,&m);for (i=1;i<=n;i++){scanf("%d",&x);if (x) add(s,i,0);else add(i,t,0);}while (m--){scanf("%d%d",&x,&y);add(x,y,1);}while (bfs())while (x=dfs(s,oo))ans+=x;printf("%d\n",ans);
}