bzoj2744[HEOI2012]朋友圈

題目鏈接：bzoj2744

題目大意：

兩個國家看成是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是朋友

求出最大朋友圈的人數

題解：

匈牙利求二分圖的最大匹配

%%%[迷の想到tarjan的我ORZ...

這個題的意思是要我們求一個圖的最大團。嗯。一定有特殊性質才使這道題可做。

首先觀察A國人，a xor b mod 2=1，就是說當且僅當這兩人一奇一偶的時候才為朋友，就是說A國的相當于一個二分圖。而二分圖的最大團只有2。

然后看B國人，可以發現，奇數間是個完全圖，偶數間也是(在先不考慮第二個條件的情況下)。那么它的補圖就是個二分圖，考慮埋第二個條件也是。而在某圖是個二分圖的前提下，其最大獨立子集就等于它補圖的最大團。于是我們構圖的時候就直接構造它的補圖，其實就是把每對奇偶都連上..(額不要忘了去掉滿足第二個條件的)。然后跑匈牙利就好了。

所以做法就是，枚舉A國選多少人(0,1,2)，哪些人。根據選出來的A國人選出能與所有被選到的A國人成為朋友的B國人，構圖(如上所述的那樣↑)，上匈牙利。因為有最大獨立子集=總點數-最大匹配，算出來后加上A國的人數就好了。

..我覺得我的代碼還是算好懂的吧，用了時間戳。嗯。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 250
#define maxm 3100int A[maxn],B[maxm];
int len,lem,bf[maxm];
int ask[maxm],tim;//用時間戳
int ln[maxm],lm[maxm];
bool bk[maxm][maxm],bo[maxn][maxm];
//bk[i][j]存B國中i,j是否突破了奇偶限制而成為了朋友
int mymax(int x,int y){return (x>y)?x:y;}
bool ffind(int x)
{int i;for (i=1;i<=lem;i++)if (ask[i]!=tim && !bk[ln[x]][lm[i]])//如果成為了朋友 那么補圖中他們兩個是不能連邊的{ask[i]=tim;if (bf[i]==-1 || ffind(bf[i])){bf[i]=x;return true;}}return false;
}
bool count(int x)
{int ret=0;while (x){if (x&1) ret++;x>>=1;}return ret&1;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n,m,r,i,j,k,x,y,ia,num,ans;scanf("%d%d%d",&n,&m,&r);for (i=1;i<=n;i++)scanf("%d",&A[i]);for (i=1;i<=m;i++)scanf("%d",&B[i]);memset(bo,false,sizeof(bo));memset(bk,false,sizeof(bk));for (i=1;i<=r;i++){scanf("%d%d",&x,&y);bo[x][y]=true;}for (i=1;i<m;i++)for (j=i+1;j<=m;j++)if ((B[i]+B[j])&1){if (count(B[i]|B[j])) bk[i][j]=bk[j][i]=true;}memset(ask,0,sizeof(ask));ans=tim=0;len=lem=num=0;for (i=1;i<=m;i++)if (B[i]&1) ln[++len]=i;else lm[++lem]=i;memset(bf,-1,sizeof(bf));for (i=1;i<=len;i++){tim++;if (ffind(i)) num++;}ans=mymax(ans,len+lem-num);for (i=1;i<=n;i++){len=lem=num=0;for (j=1;j<=m;j++)if (bo[i][j]){if (B[j]&1) ln[++len]=j;else lm[++lem]=j;}memset(bf,-1,sizeof(bf));for (j=1;j<=len;j++){tim++;if (ffind(j)) num++;}ans=mymax(ans,1+len+lem-num);}for (i=1;i<n;i++)for (j=i+1;j<=n;j++) if ((A[i]+A[j])&1){len=lem=num=0;for (k=1;k<=m;k++)if (bo[i][k] && bo[j][k]){if (B[k]&1) ln[++len]=k;else lm[++lem]=k;}memset(bf,-1,sizeof(bf));for (k=1;k<=len;k++){tim++;if (ffind(k)) num++;}ans=mymax(ans,2+len+lem-num);}printf("%d\n",ans);return 0;
}