【bzoj2744】[HEOI2012]朋友圈

2015.04.14 14:40 Tue | 4次阅读 | 旧日oi | 固定链接 | 源码

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集合中,奇数间没有边,偶数间没有边,构成了二分图,对于A中点,我们可以枚举选择情况,选0个选1个或选两个。对于每种情况,我们在反图中删掉和A中选中的点相连的B中的点,意义就是这些点一定不能选,然后跑最大匹配,答案就是B-最大匹配数-删点数+A中选的点数。
枚举A时间复杂度A^2,二分图为B*m(m为边数),当然实际效果远比这个好。注意不要反复清数组,用时间戳标记下就好

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<iomanip>
#include<cmath>
#include<queue>
#include<stack>
#define maxn 3010
#define maxm 60010
#define eps 1e-10
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long 
using namespace std;
int t,A,B,m,x,y,t1,t2,ans;
int a[maxn],b[maxn],ban[maxn],tim[maxn],vis[maxn],match[maxn];
bool map[maxn][maxn];
struct edge
{
    int to;
    int next;
    int val;
}e[maxn*maxn>>2];
int h[maxn],tp;
void ae(int u,int v,int w)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
int check(int x)
{
    int re=0;
    while(x)
    {
        re+=x&1;
        x>>=1;
    }
    return re;
}
bool dfs(int u)
{
    if(ban[u]==t1) return 0;
    for(int i=h[u];e[i].to;i=e[i].next)
    {
        int v=e[i].to;
        if(ban[v]==t1||vis[v]==t2) continue;
        vis[v]=t2;
        if(tim[v]!=t1||!match[v]||dfs(match[v]))
        {
            tim[v]=t1;
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
int get_max(int x=0,int y=0)
{
    int re=0;
    t1++;
    for(int i=1;i<=B;i++)
    if(map[x][i]||map[y][i]) 
    ban[i]=t1,re++;
    for(int i=1;i<=B;i++)
    if(b[i]&1)
    {
        t2++;
        if(dfs(i)) re++;
    }
    return B-re;
}
int main()
{
    memset(map,true,sizeof(map));
    cin>>A>>B>>m;
    for(int i=1;i<=A;i++) scanf("%d",&a[i]);
    for(int i=1;i<=B;i++) scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)
    scanf("%d%d",&x,&y),map[x][y]=0;
    for(int i=1;i<=B;i++) if(b[i]&1)
    for(int j=1;j<=B;j++) if(~b[j]&1)
    if(~check(b[i]|b[j])&1) ae(i,j,0);
    for(int i=1;i<=B;i++) map[0][i]=0;
    ans=get_max();
    for(int i=1;i<=A;i++)
    ans=max(ans,get_max(i)+1);
    for(int i=1;i<=A;i++) if(a[i]&1)
    for(int j=1;j<=A;j++) if(~a[j]&1)
    ans=max(ans,get_max(i,j)+2);
    cout<<ans<<endl;
}```