题目传送门(BZOJ)
>原文链接<

题解 :

令$S$一边赞成, $T$一边反对,

对于睡觉的从$S\to i$, 边权为$1$,表示割掉这条边冲突加$1$,

不睡觉的从$i\to T$, 边权为$1$, 意义一样.

处理好盆友的部分, 对于一对好盆友$(i, j)$, 连$(i, j, 1), (j, i, 1)$, 表示若割掉这条边使得$(i, j)$分属不同块, 冲突加$1$

求一次最小割即可

代码 :

(以前的代码, 不清真)

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int inf = 0x3f3f3f3f;#define N 2000000queue<int>q;int at[N];int nxt[N], to[N], val[N], head[N], cnt=1, dep[N];int s=N-1, t=N-2;void add_edge(int a, int b, int c) { to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; val[cnt] = c; to[++cnt] = a; nxt[cnt] = head[b]; head[b] = cnt; val[cnt] = 0;}bool bfs() { memset(dep, 0, sizeof(dep)); while(!q.empty())q.pop(); q.push(s); dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]) { if(val[i]&&!dep[to[i]]) { dep[to[i]]=dep[u]+1; if(to[i]==t)return 1; q.push(to[i]); } } } return 0;}int dfs(int p, int mf) { if(p == t)return mf; int nf = 0; for(int i = head[p];i;i = nxt[i]) { if(dep[to[i]] == dep[p]+1&&val[i]) { int tmp=dfs(to[i], min(mf-nf, val[i])); if(!tmp)dep[to[i]]=0; nf += tmp; val[i] -= tmp; val[i^1] += tmp; if(mf==nf)break; } } return nf;}void dinic() { int ans = 0, tmp; while(bfs()) { while((tmp = dfs(s, inf))) ans += tmp; } printf("%d\n", ans);}int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) scanf("%d", &at[i]); for(int i = 1; i <= n; i ++ ) { if(at[i]==1) add_edge(s, i, 1); else add_edge(i, t, 1); } for(int i = 1; i <= m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add_edge(a, b, 1); add_edge(b, a, 1); } dinic();}