BZOJ 1934 SHOI2002 善意的投票 【网络流】
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
只需要输出一个整数，即可能的最小冲突数。
Sample Input
3 3
1 0 0
1 2
1 3
3 2
1 0 0
1 2
1 3
3 2
Sample Output
1
HINT
在第一个例子中，所有小朋友都投赞成票就能得到最优解
【题解】裸题，最小割。
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <queue>
using namespace std;
const int M=300010,Ms=310;
int n,m,head[M],next[M],flow[M],to[M],c[M],tot=1,S,T;
inline void add(int u,int v,int fl) {
++tot;
next[tot]=head[u];
head[u]=tot;
to[tot]=v;
flow[tot]=fl;
}
inline void Add(int u,int v,int fl) {
add(u,v,fl);
add(v,u,0);
}
queue<int> q;
inline void qc() {
while(!q.empty()) q.pop();
}
inline bool bfs() {
qc(); memset(c,-1,sizeof(c));
q.push(S);c[S]=1;
while(!q.empty()) {
int top=q.front(); q.pop();
for (int i=head[top];i;i=next[i]) {
int _to=to[i];
if(c[_to]>=0 || flow[i]==0) continue;
c[_to]=c[top]+1;
q.push(_to);
if(_to==T) return 1;
}
}
return 0;
}
inline int dfs(int x,int low) {
if(x==T) return low;
int fl,r=low;
for (int i=head[x];i;i=next[i]) {
int _to=to[i];
if(c[_to]!=c[x]+1 || flow[i]==0) continue;
fl=dfs(_to,min(r,flow[i]));
r-=fl;
flow[i]-=fl;
flow[i^1]+=fl;
if(!r) return low;
}
if(r==low) c[x]=-1;
return low-r;
}
int main() {
scanf("%d%d",&n,&m);
S=0,T=n+1;
for (int i=1,cant;i<=n;++i) {
scanf("%d",&cant);
if(cant==1) Add(S,i,1);
else Add(i,T,1);
}
for (int i=1,u,v;i<=m;++i) {
scanf("%d%d",&u,&v);
Add(u,v,1);
Add(v,u,1);
}
int ans=0;
while(bfs()) ans+=dfs(S,200011300);
printf("%d\n",ans);
return 0;
}
评论 (0)
