思路
我们考虑将原本想同意的人连向源点，原本不同意的人连向汇点，流量皆为 \(1\)。
对于一对好朋友 \(x,y\)，我们连接 \((x,y)\) 和 \((y,x)\) 双向边，流量皆为 \(1\)。
当一个人违背自己原本的意愿时，就将它与源/汇点断边；当好朋友 \((x,y)\) 选择不同时，我们就会断掉双向边其中一条。
那么问题就是求最小割，也就是最大流。
之所以建双向边，是因为我们不知道最大流的流向是 \(x\) 向 \(y\) 还是相反。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define max(x...) max({x})
#define min(x...) min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, S, T;
struct Node
{
int to, nxt, w;
}e[200000]; int he[305], cur[305];
inline void Edge_add(int u, int v, int w)
{
static int cnt = 1;
e[++cnt] = (Node){v, he[u], w};
he[u] = cnt;
e[++cnt] = (Node){u, he[v], 0};
he[v] = cnt;
}
int bfn[305], gap[305];
queue<int> q;
inline void bfs()
{
gap[bfn[T] = 1] = 1;
q.push(T);
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = he[now]; i; i = e[i].nxt)
{
int to = e[i].to;
if(bfn[to]) continue;
gap[bfn[to] = bfn[now] + 1]++;
q.push(to);
}
}
}
int dfs(int now, int in)
{
if(now == T) return in;
int out = 0;
for(int i = cur[now]; i; i = e[i].nxt)
{
cur[now] = i;
int to = e[i].to;
if(bfn[now] != bfn[to] + 1 || !e[i].w) continue;
int re = dfs(to, min(in, e[i].w));
in -= re, out += re, e[i].w -= re, e[i ^ 1].w += re;
if(!in) return out;
}
if(!--gap[bfn[now]]) bfn[S] = T + 1;
gap[++bfn[now]]++;
return out;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = rd(), m = rd(); S = n + 1, T = n + 2;
FOR(i, 1, n)
{
int ty = rd();
if(ty) Edge_add(S, i, 1);
else Edge_add(i, T, 1);
}
FOR(i, 1, m)
{
int u = rd(), v = rd();
Edge_add(u, v, 1), Edge_add(v, u, 1);
}
bfs(); int ans = 0;
while(bfn[S] <= T)
{
memcpy(cur, he, sizeof(he));
ans += dfs(S, 1e9);
}
printf("%d", ans);
return 0;
}