「BZOJ2768」[JLOI2010]冠军调查

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了nn位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。

Input

第一行两个整数nnmm,其中n(2n300)n(2\leq n\leq 300)表示参与者的总数,m(0mn(n1)/2)m(0\leq m\leq n(n-1)/2)表示朋友的总对数。
第二行nn个整数,要么是00要么是11
如果第ii个整数的值是00的话,表示第ii个人心里认为切尔西将与冠军无缘,
如果是11的话,表示他心里认为切尔西必将夺魁。
下面mm行每行两个不同的整数,iij(1i,jn)j(1\leq i, j\leq n)表示iijj是朋友。
注意没有一对朋友会在输入中重复出现。朋友关系是双向的,并且不会传递。

Output

只有一个整数,为最小的和

Sample Input

1
2
3
4
5
3 3
1 0 0
1 2
1 3
2 3

Sample Output

1
1

Solution

如果第ii个值为00,则从ssii连容量为11的边。
否则,从ii连一条容量为11的边。
对于朋友iijj,分别连一条容量为11的边。
答案就是最大流。
考虑割的边。
割朋友边,表示冲突
SS边,表示00改变成了11
TT边,表示11改变成了00

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 310, M = N * N * 2;
int head[N], en = 1;
struct Edge {
int u, v, nxt, f;
}e[M * 2];
void addedge(int x, int y, int f) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = f;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f= 0;
}
int s, t;
int d[N];
bool bfs() {
queue<int>q;
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for(int i = head[x]; i && rest; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
k = dinic(e[i].v, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
const int inf = 1e9;
int n;
int a[N];
int main() {
n = read();
int m = read();
s = n + 1;
t = n + 2;
for(int i = 1; i <= n; ++i) {
a[i] = read();
if(a[i]) addedge(i, t, 1);
else addedge(s, i, 1);
}
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y, 1);
addedge(y, x, 1);
}
int y, ans = 0;
while(bfs()) while(y = dinic(s, inf)) ans += y;
writeln(ans);
return 0;
}