题面
题意:给你N个男生,N个女生,男生与男生之间都是朋友,女生之间也是,再给你m个关系,告诉你哪些男女是朋友,最后问你最多选几个人出来,大家互相是朋友. N最多为20
题解:很显然就像二分图了,男生一边女生一边的,然后一种解法就是
求图的最大独立集,(看起来很巧,实则也不知道为何2333)
(最大独立集是一个点集,其中任意两点在图中无对应边,对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说最大独立集=|V|-二分图的最大匹配数)
我们本来连边是,所有的朋友关系连边(男女就行了,同性都可以忽略了因为肯定可以)
但我们现在把这个图边连满,然后把有关系的边删掉,再求最大独立集,此时要求他们没有对应边不就是实际上选了那条边了吗
1 #include<bits/stdc++.h> 2 #define N 155 3 int T,n,m,x,y,used[N],g[N][N],val[N],ans; 4 using namespace std; 5 int dfs(int x) 6 { 7 for (int i=1;i<=n;i++) 8 { 9 if (g[x][i]==-1) continue; 10 if (!used[i]) 11 { 12 used[i]=1; 13 if (val[i]==-1 || dfs(val[i])) 14 { 15 val[i]=x; 16 return 1; 17 } 18 } 19 } 20 return 0; 21 } 22 int main() 23 { 24 scanf("%d",&T); 25 while(T--) 26 { 27 scanf("%d%d",&n,&m); 28 memset(g,0,sizeof(g)); 29 memset(val,-1,sizeof(val)); 30 while (m--) 31 { 32 scanf("%d%d",&x,&y); 33 g[x][y]=-1; 34 } 35 ans=2*n; 36 for (int i=1;i<=n;i++) 37 { 38 memset(used,0,sizeof(used)); 39 ans-=dfs(i); 40 } 41 printf("%d ",ans); 42 } 43 }
赛后,其他队有人写的是状态压缩dp,哈哈,一看数据范围20,确实可以直接暴力统计答案了,
f[st]表示男生状态为st的时候,女生的状态为什么(st是一个20位的数,f[st]也是哈,每位0,1表示这个人选不选)
题解直接就写在下面代码注释了
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define lld long long 4 int T,n,m,f[1<<20+1],x,y,ll[50]; 5 int main() 6 { 7 scanf("%d",&T); 8 while (T--) 9 { 10 scanf("%d%d",&n,&m); 11 int all=1<<n; 12 for (int i=0;i<all;i++) f[i]=0; 13 memset(ll,0,sizeof(ll)); 14 while (m--) 15 { 16 scanf("%d%d",&x,&y); 17 ll[x]|=(1<<(y-1));//把x的第y位变成1 18 } 19 int ans=n; 20 f[0]=all-1; 21 for (int st=1;st<all;st++) 22 { 23 int pos=__builtin_ffs(st);//返回x中最后一个为1的位是从后向前的第几位 24 f[st]=f[st^(1<<(pos-1))] & ll[pos];//st的第pos位拿出来取反 然后和这个人pos的好友状态 是否合法 25 ans=max(ans, __builtin_popcount(f[st])+__builtin_popcount(st));//f[st]表示当男生选择集合为st的时候,女生的状态 26 } 27 printf("%d ",ans); 28 } 29 }