百度之星复赛T6&&hd6149 —

Problem Description

众所周知，度度熊非常喜欢图。

它最近发现了图中也是可以出现 valley —— 山谷的，像下面这张图。

为了形成山谷，首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley。

度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。

Input

第一行为T，表示输入数据组数。

每组数据的第一行包含三个整数N，M，K，分别表示顶点个数，边的个数，标记为高点的顶点个数。

接着的M行，每行包含两个两个整数Xi，Yi，表示一条无向边。

最后一行包含K个整数Vi，表示这些点被标记为高点，其他点则都为低点。

● 1≤T≤20

● 1≤N≤30

● 1≤M≤N*(N-1)/2

● 0≤K≤min(N,15)

● 1≤Xi, Yi≤N, Xi!=Yi

● 1≤Vi≤N

Output

对每组数据输出最多能构成的valley数目。

Sample Input

Sample Output

1

0

2
——————————————————————————————————————————————————————————
果然状压dp不是很熟悉 比赛的时候没有想出来
f【i】【j】表示前i块石头 j及高点的情况
然后枚举两个高点就好辣

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,maxn=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int T,n,m,k,now,ans,cnt;

int h[M],v[M];

int f[][maxn],map[M][M];

void clear(){

    ans=; cnt=;

    memset(map,,sizeof(map));

    memset(f,,sizeof(f));

    memset(v,,sizeof(v));

}

int main()

{

    T=read();

    while(T--){

        int x,y;

        n=read(); m=read(); k=read();

        clear();

        for(int i=;i<=m;i++) x=read(),y=read(),map[x][y]=map[y][x]=;

        for(int i=;i<=k;i++) h[i]=read(),v[h[i]]=;

        int s=(<<k)-;

        for(int i=;i<=n;i++)if(!v[i]){

            now=(++cnt)&;

            memset(f[now],,sizeof(f[now]));

            for(int j=;j<=s;j++) f[now][j]=f[now^][j];

            for(int j=;j<=s;j++){

                for(int k1=;k1<=k;k1++) if(!(j&(<<(k1-)))&&map[i][h[k1]]){

                    for(int k2=k1+;k2<=k;k2++) if(!(j&(<<(k2-)))&&map[i][h[k2]]){

                        int nows=j^(<<(k1-))^(<<(k2-));

                        f[now][nows]=max(f[now][nows],f[now^][j]+);

                    }

                }

            }

        }

        for(int i=;i<=s;i++) ans=max(ans,f[now][i]);

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

    }

    return ;

}

巴特西

百度之星复赛T6&&hd6149 ——Valley Numer II

最新文章

热门文章