BZOJ 2744: [HEOI2012]朋友圈

2744: [HEOI2012]朋友圈

Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 973 Solved: 309
[Submit][Status][Discuss]

Description

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

两个国家看成是AB两国，现在是两个国家的描述：

1. A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，

那么这两个人都是朋友，否则不是；

2. B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果a xor b mod 2=0

或者 (a or b)化成二进制有奇数个1，那么两个人是朋友，否则不是朋友；

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

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

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

Input

第一行输入三个整数A,B,M，表示A国人数、B国人数、AB两国之间是朋友的对数；第二行A个数ai，表示A国第i个人的友善值；第三行B个数bi，表示B国第j个人的友善值；

第4——3+M行，每行两个整数（i，j），表示第i个A国人和第j个B国人是朋友。

Output

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

Sample Input

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

5
【样例说明】
最大朋友圈包含A国第1、2人和B国第1、2、3人。

HINT

【数据范围】

两类数据

第一类：|A|<=200 |B| <= 200

第二类：|A| <= 10 |B| <= 3000

Source

[Submit][Status][Discuss]

有点像最大团问题，但单纯那样做不了。

A国的点按照奇偶性可以分为两类，每一类内部都不是朋友，非同类的点之间均有边。

B国的点按照奇偶性也可以分为两类，每一类内部是完全图，两类之间也有一些边，可以暴力求出。

然后发现，因为A国两类点，每类点内部是不能同时选择2个点的，所以A国至多选出两个点，且这两个点分属两类，这个可以枚举。

然后，把和A国选出来的点没边的所有B国的点删掉，单看B国的反图，就成了求最大独立集的问题，而且还是二分图，匈牙利算法即可。

  1 #include <cstdio>
  2 
  3 inline char Char(void)
  4 {
  5     static const int siz = 1024;
  6     
  7     static char buf[siz];
  8     static char *hd = buf + siz;
  9     static char *tl = buf + siz;
 10     
 11     if (hd == tl)
 12         fread(hd = buf, 1, siz, stdin);
 13     
 14     return *hd++;
 15 }
 16 
 17 inline int Int(void)
 18 {
 19     int ret = 0, neg = 0, c = Char();
 20     
 21     for (; c < 48; c = Char())
 22         if (c == '-')neg ^= 1;
 23     
 24     for (; c > 47; c = Char())
 25         ret = ret * 10 + c - 48;
 26     
 27     return neg ? -ret : ret;
 28 }
 29 
 30 const int maxn = 3005;
 31 const int maxm = 9000005;
 32 
 33 int A, B, E;
 34 int a[maxn];
 35 int b[maxn];
 36 
 37 bool mp[maxn][maxn];
 38 
 39 inline int count(int x)
 40 {
 41     int ret = 0;
 42     
 43     while (x)
 44         x -= x&-x, ++ret;
 45     
 46     return ret;
 47 }
 48 
 49 inline bool check(int x, int y)
 50 {
 51     if (count(x | y) & 1)
 52         return false;
 53     
 54     return true;
 55 }
 56 
 57 int hd[maxn];
 58 int to[maxm];
 59 int nt[maxm];
 60 
 61 inline void addEdge(int x, int y)
 62 {
 63     static int tot = 0;
 64     nt[++tot] = hd[x]; to[tot] = y; hd[x] = tot;
 65 }
 66 
 67 int tim0;
 68 int tim1;
 69 int ill[maxn];
 70 int vis[maxn];
 71 int mch[maxn];
 72 
 73 bool dfs(int u)
 74 {
 75     if (u == 0)return true;
 76     
 77     for (int i = hd[u], v; i; i = nt[i])
 78         if (ill[v = to[i]] != tim0)
 79         {
 80             if (vis[v] == tim1)
 81                 continue;
 82             vis[v] = tim1;
 83             if (dfs(mch[v]))
 84             {
 85                 mch[v] = u;
 86                 return true;
 87             }
 88         }
 89     
 90     return false;
 91 }
 92 
 93 inline int calc(int x = 0, int y = 0)
 94 {
 95     int cnt = 0; ++tim0;
 96     
 97     for (int i = 1; i <= B; ++i)
 98         if (!mp[x][i] || !mp[y][i])
 99             ill[i] = tim0, ++cnt;
100                 
101     for (int i = 1; i <= B; ++i)
102         mch[i] = 0;
103     
104     for (int i = 1; i <= B; ++i)
105         if (ill[i] != tim0)
106         {
107             ++tim1;
108             
109             if (dfs(i))
110                 ++cnt;
111         }
112     
113     return B - cnt;
114 }
115 
116 signed main(void)
117 {
118     A = Int();
119     B = Int();
120     E = Int();
121     
122     for (int i = 1; i <= A; ++i)
123         a[i] = Int();
124     
125     for (int i = 1; i <= B; ++i)
126         b[i] = Int();
127     
128     for (int i = 1; i <= E; ++i)
129     {
130         int x = Int();
131         int y = Int();
132         mp[x][y] = true;
133     }
134     
135     for (int i = 1; i <= B; ++i)
136         mp[0][i] = true;
137     
138     for (int i = 1; i <= B; ++i)if (b[i] & 1)
139         for (int j = 1; j <= B; ++j)if (!(b[j] & 1))
140             if (check(b[i], b[j]))addEdge(i, j);
141     
142     int ans = calc();
143     
144     for (int i = 1; i <= A; ++i)
145     {
146         int tmp = calc(i) + 1;
147         if (tmp > ans)
148             ans = tmp;
149     }
150     
151     for (int i = 1; i <= A; ++i)if (a[i] & 1)
152         for (int j = 1; j <= A; ++j)if (!(a[j] & 1))
153         {
154             int tmp = calc(i, j) + 2;
155             if (tmp > ans)
156                 ans = tmp;
157         }
158         
159     printf("%d
", ans);
160 }

@Author: YouSiki