1 #include<cstdio> 2 #include<iostream> 3 #define M 3010 4 using namespace std; 5 int A,B,m,a[M],b[M],map[M][M],head[M],next[M*M>>2],u[M*M>>2],cnt,ans,f1,f2,ban[M],f[M],k[M],pi[M]; 6 int ji(int a1) 7 { 8 int sum=0; 9 for(;a1;) 10 { 11 a1-=a1&-a1; 12 sum++; 13 } 14 return sum; 15 } 16 void jia(int a1,int a2) 17 { 18 cnt++; 19 next[cnt]=head[a1]; 20 head[a1]=cnt; 21 u[cnt]=a2; 22 return; 23 } 24 bool xun(int a1) 25 { 26 for(int i=head[a1];i;i=next[i]) 27 if(ban[u[i]]<f1&&f[u[i]]<f2) 28 { 29 f[u[i]]=f2; 30 if(k[u[i]]<f1||!pi[u[i]]||xun(pi[u[i]])) 31 { 32 k[u[i]]=f1; 33 pi[u[i]]=a1; 34 return 1; 35 } 36 } 37 return 0; 38 } 39 int make(int x=0,int y=0) 40 { 41 int re=0; 42 f1++; 43 for(int i=1;i<=B;i++) 44 if(!map[x][i]||!map[y][i]) 45 { 46 ban[i]=f1; 47 re++; 48 } 49 for(int i=1;i<=B;i++) 50 if(b[i]&1&&ban[i]<f1) 51 { 52 f2++; 53 if(xun(i)) 54 re++; 55 } 56 return B-re; 57 } 58 int main() 59 { 60 scanf("%d%d%d",&A,&B,&m); 61 for(int i=1;i<=A;i++) 62 scanf("%d",&a[i]); 63 for(int i=1;i<=B;i++) 64 scanf("%d",&b[i]); 65 for(int i=1;i<=m;i++) 66 { 67 int a1,a2; 68 scanf("%d%d",&a1,&a2); 69 map[a1][a2]=1; 70 } 71 for(int i=1;i<=B;i++) 72 map[0][i]=1; 73 for(int i=1;i<=B;i++) 74 if(b[i]&1) 75 for(int j=1;j<=B;j++) 76 if(~b[j]&1) 77 if(~ji(b[i]|b[j])&1) 78 jia(i,j); 79 ans=make(); 80 for(int i=1;i<=A;i++) 81 ans=max(make(i)+1,ans); 82 for(int i=1;i<=A;i++) 83 if(a[i]&1) 84 for(int j=1;j<=A;j++) 85 if(~a[j]&1) 86 ans=max(make(i,j)+2,ans); 87 printf("%d ",ans); 88 return 0; 89 }
由题A国只能取两个，一奇一偶。求最大团，最大团=补图最大独立子集。B国补图是一个二分图。枚举A国的点，在B国上跑最大独立子集=节点数-最大匹配数。