2744: [HEOI2012]朋友圈
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 612 Solved: 174
[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
第一行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
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人。
【样例说明】
最大朋友圈包含A国第1、2人和B国第1、2、3人。
HINT
【数据范围】
两类数据
第一类：|A|<=200 |B| <= 200
第二类：|A| <= 10 |B| <= 3000
说实话这个数据范围我并不会正解，但是这道题，枚举A过的点（最多两个），对B国跑匈牙利是可以过的，只是提醒一个坑：出题人貌似专门卡了匈牙利，如果TLE掉了试一试换一个集合调用find函数。原来我在b[i]%2==0时调用find(i)TLE，然后换成b[i]%2==1就行了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define MAXN 3100
#define MAXV MAXN
#define MAXE 11000000
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y)
{
E[++tope].np=y;
E[tope].next=V[x];
V[x]=&E[tope];
}
vector<int> blst[MAXN];
int a[MAXN],b[MAXN];
int vis[MAXN],vistime;
int ptr[MAXN];
bool find(int now)
{
if (vis[now]==vistime)return false;
vis[now]=vistime;
Edge *ne;
for (ne=V[now];ne;ne=ne->next)
{
if (ptr[ne->np]==- || find(ptr[ne->np]))
{
ptr[ne->np]=now;
return true;
}
}
return false;
}
int work(vector<int> seq)
{
for (int i=;i<seq.size();i++)ptr[seq[i]]=-;
for (int i=;i<seq.size();i++)
{
for (int j=i+;j<seq.size();j++)
{
if (((b[seq[i]]^b[seq[j]])&) && !__builtin_parity(b[seq[i]]|b[seq[j]]))
{
addedge(seq[i],seq[j]);
addedge(seq[j],seq[i]);
}
}
}
int ret=;
for (int i=;i<seq.size();i++)
{
if ((b[seq[i]]&))
{
++vistime;
ret+=find(seq[i]);
}
}
ret=seq.size()-ret;
for (int i=;i<seq.size();i++)V[seq[i]]=;tope=-;
return ret;
} int ans=;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n,m,q;
int x,y;
vector<int> seq;
scanf("%d%d",&n,&m);
scanf("%d",&q);
for (int i=;i<=n;i++)
scanf("%d",a+i);
for (int i=;i<=m;i++)
scanf("%d",b+i);
for (int i=;i<=n;i++)blst[i].clear();
for (int i=;i<=q;i++)
{
scanf("%d%d",&x,&y);
blst[x].push_back(y);
}
for (int i=;i<=n;i++)
{
sort(blst[i].begin(),blst[i].end());
blst[i].erase(unique(blst[i].begin(),blst[i].end()),blst[i].end());
}
//Nothing In A
for (int i=;i<=m;i++)seq.push_back(i);
ans=max(ans,work(seq));
seq.clear();
for (int i=;i<=n;i++)
{
for (int j=;j<blst[i].size();j++)
seq.push_back(blst[i][j]);
if (seq.size()+>ans)
ans=max(ans,work(seq)+);
seq.clear();
}
for (int i=;i<=n;i++)
{
for (int j=i+;j<=n;j++)
{
if (!((a[i]^a[j])&))continue;
vector<int> :: iterator it1,it2;
it1=blst[i].begin();
it2=blst[j].begin();
while (it1!=blst[i].end() && it2!=blst[j].end())
{
if (*it1==*it2)
{
seq.push_back(*it1);
it1++,it2++;
}else if (*it1<*it2)
{
it1++;
}else
{
it2++;
}
}
if (seq.size()+>ans)
ans=max(ans,work(seq)+);
seq.clear();
}
}
printf("%d\n",ans);
}