【BZOJ 2744 】[HEOI2012]朋友圈

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

第一行t<=6,表示输入数据总数。

接下来t个数据：

第一行输入三个整数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

原来二分图还能这么玩？我觉得这个题还是相当神的。。。果真我很弱

对于A国显然可得奇数和偶数之间有边，对于B国，奇数和奇数之间有边，偶数和偶数之间有边，奇数和偶数之可能有边

根据定义，就是求这张图上的最大团

如何求最大团？据说这是一个相当神的NP问题，可以用搜索解，显然这样不行

对于这个题来说

建立反图

我们可以发现A国的同种数之间构成了一张完全图，B国则构成一张二分图

由某个定理求一个图的最大团等于求一张图反图的最大独立集（我不知道这样说对不对，反正对这个题来说是对的）

因为是最大独立集，A图中的人至多选两个，B图中把反图中和A国相连的边删掉，然后跑最大独立集。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct ee{int to,next;}e[N*N];

 bool map[N][N],vis[N],visit[N];

 int b[N],a[N],a1[N],a2[N],head[N],link[N];

 int ans,A,B,M,cnt,n1,n2,T;

 void ins(int u,int v){

     e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt;

 }

 bool check(int x){

     if (vis[x]) return ;

     for (int i=head[x];i;i=e[i].next){

         int v=e[i].to;

         if (!vis[v]&&!visit[v]){

             vis[v]=;

             if (!link[v]||check(link[v])){

                 link[v]=x;

                 return ;

             }

         }

     }

     return ;

 }

 int main(){

     {

     scanf("%d%d%d",&A,&B,&M);

     for (int i=;i<=A;i++) {

         scanf("%d",&a[i]);

         if (a[i]&==) a1[++n1]=i;else a2[++n2]=i;

     }

     for (int i=;i<=B;i++) scanf("%d",&b[i]);

     memset(map,true,sizeof(map));

     int u,v;

     for (int i=;i<=M;i++){

         scanf("%d%d",&u,&v);

         map[u][v]=; map[v][u]=;

     }

     for (int i=;i<=B;i++)

         for (int j=i+;j<=B;j++){

             if(i==j) continue;

             if (!((b[i]^b[j])&))continue;

             else{

                 int t=;

                 for (int k=;<<k<=(b[i]|b[j]);k++)

                     if ((b[i]|b[j])&(<<k)) t++;

                 if (t%==) ins(i,j),ins(j,i);

             }

         }

     for (int i=;i<=B;i++)map[i][]=,map[][i]=;

     for (int i=;i<=n1;i++)

         for (int j=;j<=n2;j++){

             int t=;

             int x=a1[i],y=a2[j];

             memset(visit,,sizeof(visit));

             memset(link,,sizeof(link));

             for (int k=;k<=B;k++)if (map[x][k]||map[y][k]) visit[k]=,t++;

             for (int k=;k<=B;k++)

             if (b[k]&==&&!visit[k]){

                 memset(vis,,sizeof(vis));

                 if (check(k)) t++;

             }

             if (i) t--;if (j) t--;

             ans=max(ans,B-t);

         }

     printf("%d",ans);

     }

 }

秒客网