HDU 6149 Valley Numer II (状压DP 易错题)

题目大意：给你一个无向连通图(n<=30)，点分为高点和低点，高点数量<=15，如果两个高点和低点都直接连边，那么我们称这三个点形成一个valley，每个点最多作为一个valley的组成部分，求valley的最大数量

高点状压，然后枚举低点，判断这个低点能否影响答案

注意：上一层的值要全都先赋给这一层，再枚举这一层，否则上一层的某些状态可能还没枚举到就枚举这一层了

(比如上一层可行的状态是0110，这一层新来了1001，我们要先把0110和1001赋给这一层，否则我们在从小到大先枚举0110时，这一层的状态0110以及1001并没有被上一层更新，导致转移出错

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #define N 35

 using namespace std;

 int T,n,m,K,cnt;

 int d[N][N],up[N],dn[N],use[N];

 int f[][(<<)+];

 void clr()

 {

     memset(d,,sizeof(d));

     memset(up,,sizeof(up));

     memset(dn,,sizeof(dn));

     memset(use,,sizeof(use));

     memset(f,,sizeof(f));

     cnt=;

 }

 int main()

 {

     //freopen("aa.in","r",stdin);

     scanf("%d",&T);

     while(T--)

     {

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

         clr();

         int x,y;

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

         {

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

             d[x-][y-]=d[y-][x-]=;

         }

         for(int k=;k<K;k++)

         {

             scanf("%d",&x);

             up[k]=x-;

             use[x-]=;

         }

         for(int i=;i<n;i++) if(!use[i]) dn[++cnt]=i;

         for(int k=;k<=cnt;k++) f[k][]=;

         for(int k=;k<=cnt;k++)

         {

             for(int s=;s<(<<K);s++) {f[k][s]=f[k-][s];}

             for(int s=;s<(<<K);s++)

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

                     if(!((<<i)&s)&&d[up[i]][dn[k]])

                         for(int j=;j<K;j++)

                             if(i!=j&&!((<<j)&s)&&d[dn[k]][up[j]])

                                 f[k][s|(<<i)|(<<j)] = max(f[k][s|(<<i)|(<<j)],f[k-][s]+);

         }

         int ans=;

         for(int s=;s<(<<K);s++)

             ans=max(ans,f[cnt][s]);

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

     }

     return ;

 }

巴特西

HDU 6149 Valley Numer II (状压DP 易错题)

最新文章

热门文章