Gym-101915D Largest Group 最大独立集 Or 状态压缩DP

题面
题意:给你N个男生,N个女生,男生与男生之间都是朋友,女生之间也是,再给你m个关系,告诉你哪些男女是朋友,最后问你最多选几个人出来,大家互相是朋友. N最多为20

题解:很显然就像二分图了,男生一边女生一边的,然后一种解法就是

求图的最大独立集,(看起来很巧,实则也不知道为何2333)

(最大独立集是一个点集,其中任意两点在图中无对应边,对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说最大独立集=|V|-二分图的最大匹配数)

我们本来连边是,所有的朋友关系连边(男女就行了,同性都可以忽略了因为肯定可以)

但我们现在把这个图边连满,然后把有关系的边删掉,再求最大独立集,此时要求他们没有对应边不就是实际上选了那条边了吗

 #include<bits/stdc++.h>

 #define N 155

 int T,n,m,x,y,used[N],g[N][N],val[N],ans;

 using namespace std;

 int dfs(int x)

 {

     for (int i=;i<=n;i++)

     {

         if (g[x][i]==-) continue;

         if (!used[i])

         {

             used[i]=;

             if (val[i]==- || dfs(val[i]))

             {

                 val[i]=x;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         memset(g,,sizeof(g));

         memset(val,-,sizeof(val));

         while (m--)

         {

             scanf("%d%d",&x,&y);

             g[x][y]=-;

         }

         ans=*n;

         for (int i=;i<=n;i++)

         {

             memset(used,,sizeof(used));

             ans-=dfs(i);

         }

         printf("%d\n",ans);

     }

 }

赛后,其他队有人写的是状态压缩dp,哈哈,一看数据范围20,确实可以直接暴力统计答案了,

f[st]表示男生状态为st的时候,女生的状态为什么(st是一个20位的数,f[st]也是哈,每位0,1表示这个人选不选)

题解直接就写在下面代码注释了

 #include<bits/stdc++.h>

 using namespace std;

 #define lld long long

 int T,n,m,f[<<+],x,y,ll[];

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d%d",&n,&m);

         int all=<<n;

         for (int i=;i<all;i++) f[i]=;

         memset(ll,,sizeof(ll));

         while (m--)

         {

             scanf("%d%d",&x,&y);

             ll[x]|=(<<(y-));//把x的第y位变成1

         }

         int ans=n;

         f[]=all-;

         for (int st=;st<all;st++)

         {

             int pos=__builtin_ffs(st);//返回x中最后一个为1的位是从后向前的第几位

             f[st]=f[st^(<<(pos-))] & ll[pos];//st的第pos位拿出来取反 然后和这个人pos的好友状态 是否合法

             ans=max(ans, __builtin_popcount(f[st])+__builtin_popcount(st));//f[st]表示当男生选择集合为st的时候,女生的状态

         }

         printf("%d\n",ans);

      }

 }

巴特西

Gym-101915D Largest Group 最大独立集 Or 状态压缩DP

最新文章

热门文章