「BZOJ2744」 HEOI2012 朋友圈 题解

问题

原题链接 BZOJ2744

Description

在很久很久以前,曾经有两个国家和睦相处,无忧无虑的生活着。一年一度的评比大会开始了,作为和平的两国,一个朋友圈数量最多的永远都是最值得他人的尊敬,所以现在就是需要你求朋友圈的最大数目。
两个国家看成是AB两国,现在是两个国家的描述:

  1. A国:每个人都有一个友善值,当两个A国人的友善值a、b,如果 axorb1(mod2)a xor b \equiv 1 \pmod 2
    那么这两个人都是朋友,否则不是;

  2. B国:每个人都有一个友善值,当两个B国人的友善值a、b,如果 axorb0(mod2)a xor b \equiv 0 \pmod 2 或者 (aorb)(a or b) 化成二进制有奇数个 11 ,那么两个人是朋友,否则不是朋友;

  3. A、B两国之间的人也有可能是朋友,数据中将会给出A、B之间“朋友”的情况。

  4. 在AB两国,朋友圈的定义:一个朋友圈集合S,满足 SABS \in A \cup B,对于所有的 i,jSi, j \in Siijj 是朋友

由于落后的古代,没有电脑这个也就成了每年最大的难题,而你能帮他们求出最大朋友圈的人数吗?

Input

第一行 t6t \leq 6 ,表示输入数据总数。
接下来 tt 个数据:
第一行输入三个整数 A,B,MA,B,M ,表示A国人数、B国人数、AB两国之间是朋友的对数;第二行 AA 个数 aia_i ,表示A国第 ii 个人的友善值;第三行 BB 个数 bib_i ,表示B国第 jj 个人的友善值;
443+M3 + M 行,每行两个整数 i,ji, j ,表示第 ii 个A国人和第 jj 个B国人是朋友。

Output

输出 tt 行,每行,输出一个整数,表示最大朋友圈的数目。

Sample Input

Input
1
2
3
4
5
6
7
8
9
10
2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4

Sample Output

Output
1
5

样例说明

最大朋友圈包含A国第1、2人和B国第1、2、3人。

数据范围

两类数据

第一类: A200B200|A| \leq 200, |B| \leq 200

第二类: A10B3000|A| \leq 10, |B| \leq 3000

解题

题目中提到求最大团,可以联想到在二分图中求最大独立集。

只考虑每个国家内部的人物关系,以每个人之间的关系建边可以建出 A B 两张图,通过观察这两张图,可以发现 B 图的补图是二分图,并且朋友圈中 A 图包含的人数只有三种可能 0,1,20,1,2 ,所以可以枚举选择 A 图中所有选择的情况,并且将与所选出的 A 图中的点没有连边的 B 图中的点全部删除,并在 B 的补图中,对剩下的点求最大独立集,补图中的最大独立集大小就等于原图中的最大团大小。

需要注意的是,这里匈牙利算法需要进行时间戳优化,否则会 TLE 。并且,虽然题目中说有多组测试数据,但是观察样例数据与提交代码测试,这道题的所有测试点都只有一组数据,并且不需要输入数据组数。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3000 + 5;
const int MAXM = 9e6 + 5;
struct Edge {
int e, next;
}ed[MAXM];
int first[MAXN], en;
inline void add_edge(int s, int e) {
en++;
ed[en].next = first[s];
first[s] = en;
ed[en].e = e;
}
int va[MAXN], vb[MAXN];
int a, b, m, ut;
inline bool bin(int x, int y) {
int tmp = x | y;
int res = 0;
while(tmp) {
if(tmp & 1) res++;
tmp >>= 1;
}
return res & 1;
}
bool del[MAXN];
int use[MAXN], result[MAXN];
bool dfs(int i) {
if(use[i] == ut) return false;
for(register int j = first[i]; j; j = ed[j].next) {
int e = ed[j].e;
if(use[e] != ut && !del[e]) {
use[e] = ut;
if(!result[e] || dfs(result[e])) {
result[e] = i;
return true;
}
}
}
return false;
}
inline int xiongyali(int bnow) {
int ans = 0;
memset(result, 0, sizeof(result));
for(register int i = 1; i <= b; i++) {
if(del[i] == true || !(vb[i] & 1)) continue;
ut++;
if(dfs(i)) ans++;
}
return bnow - ans;
}
bool ab[205][3005];
int main() {
int tk;
register int i, j, l, u, v;
tk = 1;
for(int t = 1; t <= tk; t++) {
cin >> a >> b >> m;
memset(first, 0, sizeof(first));
en = 0;
for(i = 1; i <= a; i++) cin >> va[i];
for(i = 1; i <= b; i++) cin >> vb[i];
for(i = 1; i <= m; i++) {
cin >> u >> v;
ab[u][v] = true;
}
for(i = 1; i <= b; i++) {
if(vb[i] & 1) {
for(j = 1; j <= b; j++) {
if(!(vb[j] & 1)) {
if(!bin(vb[i], vb[j])) {
add_edge(i, j);
add_edge(j, i);
}
}
}
}
}
memset(del, 0, sizeof(del));
int ans = xiongyali(b);
for(i = 1; i <= a; i++) {
int bnow = b;
memset(del, 0, sizeof(del));
for(j = 1; j <= b; j++) {
if(ab[i][j] != true) {
del[j] = true;
bnow--;
}
}
ans = max(ans, xiongyali(bnow) + 1);
}
for(i = 1; i <= a; i++) {
if(va[i] & 1) continue;
for(j = 1; j <= a; j++) {
if(!(va[j] & 1)) continue;
int bnow = b;
memset(del, 0, sizeof(del));
for(l = 1; l <= b; l++) {
if(ab[i][l] != true || ab[j][l] != true) {
del[l] = true;
bnow--;
}
}
ans = max(ans, xiongyali(bnow) + 2);
}
}
cout << ans << endl;
}
return 0;
}