bzoj 2744: [HEOI2012]朋友圈二分图匹配

mac2022-07-05 30

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

Sample Output

5 【样例说明】最大朋友圈包含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=-1; 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]==-1 || find(ptr[ne->np])) { ptr[ne->np]=now; return true; } } return false; } int work(vector<int> seq) { for (int i=0;i<seq.size();i++)ptr[seq[i]]=-1; for (int i=0;i<seq.size();i++) { for (int j=i+1;j<seq.size();j++) { if (((b[seq[i]]^b[seq[j]])&1) && !__builtin_parity(b[seq[i]]|b[seq[j]])) { addedge(seq[i],seq[j]); addedge(seq[j],seq[i]); } } } int ret=0; for (int i=0;i<seq.size();i++) { if ((b[seq[i]]&1)) { ++vistime; ret+=find(seq[i]); } } ret=seq.size()-ret; for (int i=0;i<seq.size();i++)V[seq[i]]=0;tope=-1; return ret; } int ans=0; 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=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=m;i++) scanf("%d",b+i); for (int i=1;i<=n;i++)blst[i].clear(); for (int i=1;i<=q;i++) { scanf("%d%d",&x,&y); blst[x].push_back(y); } for (int i=1;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=1;i<=m;i++)seq.push_back(i); ans=max(ans,work(seq)); seq.clear(); for (int i=1;i<=n;i++) { for (int j=0;j<blst[i].size();j++) seq.push_back(blst[i][j]); if (seq.size()+1>ans) ans=max(ans,work(seq)+1); seq.clear(); } for (int i=1;i<=n;i++) { for (int j=i+1;j<=n;j++) { if (!((a[i]^a[j])&1))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()+2>ans) ans=max(ans,work(seq)+2); seq.clear(); } } printf("%d\n",ans); }

转载于:https://www.cnblogs.com/mhy12345/p/4759108.html

最新回复(0)

bzoj 2744: [HEOI2012]朋友圈 二分图匹配