「BZOJ2744」 HEOI2012 朋友圈 题解

问题

原题链接 BZOJ2744

Description

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

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

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

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

  4. 在AB两国，朋友圈的定义：一个朋友圈集合S，满足 S∈A∪BS \in A \cup B，对于所有的 i,j∈Si, j \in S ，ii 和 jj 是朋友

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

Input

第一行 t≤6t \leq 6 ，表示输入数据总数。
接下来 tt 个数据：
第一行输入三个整数 A,B,MA,B,M ，表示A国人数、B国人数、AB两国之间是朋友的对数；第二行 AA 个数 aia_i ，表示A国第 ii 个人的友善值；第三行 BB 个数 bib_i ，表示B国第 jj 个人的友善值；
第 44 至 3+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人。

数据范围

两类数据

第一类： ∣A∣≤200，∣B∣≤200|A| \leq 200， |B| \leq 200

第二类： ∣A∣≤10，∣B∣≤3000|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
111
#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;
}