Valley Numer II 题解(状压dp)

题目链接

题目大意

给定一张 N 个点 M 条边的无向图，其中有 K 个点被标记为高点，剩下的 (N-K) 个点是低点。图中的山谷

定义为三元组 <X,Y,Z>，满足X和Y之间有边，Y与 Z之间也有边，同时X和Z是高点，Y是低点。问这个图中

最多有几个山谷（一个点只能出现在一个山谷中）

N ≤ 30, K ≤ min(N,15)

题目思路

高点的数量很少，那么可以想到把高点状态压缩

$dp[i][s] $表示前 i 个低点，使用过的高点的状态为 s 的情况下，组成的山谷的最大可能值。

转移(dp[i][s]) 的时候，取出第 i+1 个低点。枚举不在 s 中的两个高点 p 和 q.检查 p 和 q 和第 i+1 个低点

能否配对。如果可以，那么就可以用$ dp[i][s] + 1$ 去更新(dp[i + 1][s | (1 << p) | (1 << q)] )答案就是

$max ;dp[n-k][i] | 0 ≤ i < 2^k $

然后再把可以预处理的东西都预处理一下

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=30+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m,k;
int e[maxn][maxn];
int dp[maxn][1<<15];
int h[maxn];
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            h[i]=0;
            for(int j=1;j<=n;j++){
                e[i][j]=0;
            }
        }
        for(int i=1,x,y;i<=m;i++){
            scanf("%d%d",&x,&y);
            e[x][y]=e[y][x]=1;
        }
        for(int i=1,x;i<=k;i++){
            scanf("%d",&x);
            h[x]=1;
        }
        vector<int> a,b;
        for(int i=1;i<=n;i++){
            if(h[i]){// 高点
                b.push_back(i);
            }else{ //低点
                a.push_back(i);
            }
        }
        vector<pair<int,int> > vec[maxn];
        for(int i=0;i<a.size();i++){
            int x=a[i];
            for(int j=0;j<b.size();j++){
                int y=b[j];
                for(int k=j+1;k<b.size();k++){
                    int z=b[k];
                    if(e[x][y]&&e[x][z]){
                        vec[i].push_back({j,k});
                    }
                }
            }
        }
        int sza=a.size();
        int szb=b.size();
        for(int i=0;i<=sza;i++){
            for(int j=0;j<=(1<<szb);j++){
                dp[i][j]=-inf;
            }
        }
        dp[0][0]=0;
        for(int i=0;i<sza;i++){
            for(int j=0;j<=(1<<szb)-1;j++){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
                for(auto temp:vec[i]){
                    int x=temp.fi;
                    int y=temp.se;
                    if(!(j&(1<<x))&&(!(j&(1<<y)))){
                        dp[i+1][j|(1<<x)|(1<<y)]=max(dp[i+1][j|(1<<x)|(1<<y)],dp[i][j]+1);
                    }
                }
            }
        }
        int ans=0;
        for(int j=0;j<=(1<<szb)-1;j++){
            ans=max(ans,dp[sza][j]);
        }
        printf("%d
",ans);
    }
    return 0;
}