首页 > 代码库 > BZOJ 2744: [HEOI2012]朋友圈

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\n", ans);160 }

 

@Author: YouSiki

BZOJ 2744: [HEOI2012]朋友圈