BZOJ1934[Shoi2007]善意投票问题的最小割解决方案

题目

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

输入格式

第一行只有两个整数n&＃xff0c;m&＃xff0c;保证有2≤n≤300&＃xff0c;1≤m≤n(n-1)/2。其中n代表总人数&＃xff0c;m代表好朋友的对数。文件第二行有n个整数&＃xff0c;第i个整数代表第i个小朋友的意愿&＃xff0c;当它为1时表示同意睡觉&＃xff0c;当它为0时表示反对睡觉。接下来文件还有m行&＃xff0c;每行有两个整数i&＃xff0c;j。表示i&＃xff0c;j是一对好朋友&＃xff0c;我们保证任何两对i&＃xff0c;j不会重复。

输出格式

只需要输出一个整数&＃xff0c;即可能的最小冲突数。

输入样例

3 3

1 0 0

1 2

1 3

3 2

输出样例

1

解释

在第一个例子中&＃xff0c;所有小朋友都投赞成票就能得到最优解

题解

我们设源汇点S、T&＃xff0c;S向赞成的小朋友连边&＃xff0c;不赞成的向T连边&＃xff0c;好友之间互相连边&＃xff0c;容量均为1
此时求最小割即为答案
对于任意一一对好友&＃xff0c;他们要么在同一边&＃xff0c;要么二者断开【好友冲突】&＃xff0c;要么其中一者与源汇点断开【改变意愿】

#include
#include
#include
#include
#include
#define LL long long int
#define REP(i,n) for (int i &＃61; 1; i <&＃61; (n); i&＃43;&＃43;)
#define Redge(u) for (int k &＃61; h[u]; k !&＃61; -1; k &＃61; ed[k].nxt)
using namespace std;
const int maxn &＃61; 305,maxm &＃61; 300005,INF &＃61; 1000000000;
inline int RD(){int out &＃61; 0,flag &＃61; 1; char c &＃61; getchar();while (c <48 || c > 57) {if (c &＃61;&＃61; &＃39;-&＃39;) flag &＃61; -1; c &＃61; getchar();}while (c >&＃61; 48 && c <&＃61; 57) {out &＃61; (out <<1) &＃43; (out <<3) &＃43; c - &＃39;0&＃39;; c &＃61; getchar();}return out * flag;
}
int h[maxn],ne &＃61; 0,N,M,d[maxn],vis[maxn],cur[maxn],S,T;
struct EDGE{int to,nxt,f;}ed[maxm];
inline void build(int u,int v,int w){ed[ne] &＃61; (EDGE){v,h[u],w}; h[u] &＃61; ne&＃43;&＃43;;ed[ne] &＃61; (EDGE){u,h[v],0}; h[v] &＃61; ne&＃43;&＃43;;
}
bool bfs(){queue<int> q;for (int i &＃61; S; i <&＃61; T; i&＃43;&＃43;) vis[i] &＃61; false,d[i] &＃61; INF;d[S] &＃61; 0; q.push(S); int to,u;while (!q.empty()){u &＃61; q.front(); q.pop();Redge(u) if (ed[k].f && !vis[to &＃61; ed[k].to]){d[to] &＃61; d[u] &＃43; 1; vis[to] &＃61; true;q.push(to);}}return vis[T];
}
int dfs(int u,int minf){if (u &＃61;&＃61; T || !minf) return minf;int flow &＃61; 0,f,to;if (cur[u] &＃61;&＃61; -2) cur[u] &＃61; h[u];for (int& k &＃61; cur[u]; k !&＃61; -1; k &＃61; ed[k].nxt)if (d[to &＃61; ed[k].to] &＃61;&＃61; d[u] &＃43; 1 && (f &＃61; dfs(to,min(minf,ed[k].f)))){ed[k].f -&＃61; f; ed[k ^ 1].f &＃43;&＃61; f;flow &＃43;&＃61; f; minf -&＃61; f;if (!minf) break;}return flow;
}
int maxflow(){int flow &＃61; 0;while (bfs()){fill(cur,cur &＃43; maxn,-2);flow &＃43;&＃61; dfs(S,INF);}return flow;
}
int main(){memset(h,-1,sizeof(h));N &＃61; RD(); M &＃61; RD(); S &＃61; 0; T &＃61; N &＃43; 1; int a,b;REP(i,N) if (RD()) build(S,i,1); else build(i,T,1);while (M--){a &＃61; RD(); b &＃61; RD();build(a,b,1); build(b,a,1);}printf("%d",maxflow());return 0;
}