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國相連的邊刪掉，然后跑最大獨立集。

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=3050; 6 struct ee{int to,next;}e[N*N]; 7 bool map[N][N],vis[N],visit[N]; 8 int b[N],a[N],a1[N],a2[N],head[N],link[N]; 9 int ans,A,B,M,cnt,n1,n2,T; 10 void ins(int u,int v){ 11 e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt; 12 } 13 14 bool check(int x){ 15 if (vis[x]) return 0; 16 for (int i=head[x];i;i=e[i].next){ 17 int v=e[i].to; 18 if (!vis[v]&&!visit[v]){ 19 vis[v]=1; 20 if (!link[v]||check(link[v])){ 21 link[v]=x; 22 return 1; 23 } 24 } 25 } 26 return 0; 27 } 28 29 int main(){ 30 { 31 scanf("%d%d%d",&A,&B,&M); 32 for (int i=1;i<=A;i++) { 33 scanf("%d",&a[i]); 34 if (a[i]&1==1) a1[++n1]=i;else a2[++n2]=i; 35 } 36 for (int i=1;i<=B;i++) scanf("%d",&b[i]); 37 memset(map,true,sizeof(map)); 38 int u,v; 39 for (int i=1;i<=M;i++){ 40 scanf("%d%d",&u,&v); 41 map[u][v]=0; map[v][u]=0; 42 } 43 for (int i=1;i<=B;i++) 44 for (int j=i+1;j<=B;j++){ 45 if(i==j) continue; 46 if (!((b[i]^b[j])&1))continue; 47 else{ 48 int t=0; 49 for (int k=0;1<<k<=(b[i]|b[j]);k++) 50 if ((b[i]|b[j])&(1<<k)) t++; 51 if (t%2==0) ins(i,j),ins(j,i); 52 } 53 } 54 for (int i=0;i<=B;i++)map[i][0]=0,map[0][i]=0; 55 for (int i=0;i<=n1;i++) 56 for (int j=0;j<=n2;j++){ 57 int t=0; 58 int x=a1[i],y=a2[j]; 59 memset(visit,0,sizeof(visit)); 60 memset(link,0,sizeof(link)); 61 for (int k=1;k<=B;k++)if (map[x][k]||map[y][k]) visit[k]=1,t++; 62 for (int k=1;k<=B;k++) 63 if (b[k]&1==1&&!visit[k]){ 64 memset(vis,0,sizeof(vis)); 65 if (check(k)) t++; 66 } 67 if (i) t--;if (j) t--; 68 ans=max(ans,B-t); 69 } 70 printf("%d",ans); 71 } 72 }

?

?

轉載于:https://www.cnblogs.com/wuminyan/p/5189853.html

總結

以上是生活随笔為你收集整理的【BZOJ 2744 】[HEOI2012]朋友圈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。