http://acm.hdu.edu.cn/showproblem.php?pid=6149

---

思路：

将图的相关点变成序列。

对于每个点，搜出匹配的山峰状态s。采用递推，i的s状态，搜出两个没用过的点，更新dp[i+1][s|1<<(p-1)|1<<(q-1)]，类似01背包，看是否能在现在的基础上+1

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=35;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
bool vis[maxn];
LL high[maxn],cnt=0;
LL low[maxn],tot=0;
LL ma[maxn][maxn];
LL dp[maxn][(1<<16)+1000];
int main(void){
   cin.tie(0);std::ios::sync_with_stdio(false);
   LL t;cin>>t;
   while(t--){
      memset(ma,0,sizeof(ma));memset(vis,0,sizeof(vis));
      memset(low,0,sizeof(low));memset(high,0,sizeof(high));
      memset(dp,0,sizeof(dp));
      cnt=tot=0;
      LL n,m,k;cin>>n>>m>>k;
      for(LL i=1;i<=m;i++){
          LL u,v;cin>>u>>v;ma[u][v]=ma[v][u]=1;
      }
      for(LL i=1;i<=k;i++){
          LL x;cin>>x;
          vis[x]=1;
      }
      for(LL i=1;i<=n;i++){
          if(vis[i]) high[++cnt]=i;
          if(!vis[i]) low[++tot]=i;
      }
      ///预处理
      vector< pair<LL,LL> > trans[35];
      for(LL i=1;i<=tot;i++){
          for(LL p=1;p<=cnt;p++){
              if(!ma[low[i]][high[p]]) continue;
              for(LL q=p+1;q<=cnt;q++){
                  if(!ma[low[i]][high[q]]) continue;
                  trans[i].push_back({p,q});
                  ///dp[i][ (1<<(p-1) )| ( 1<<(q-1) )]=1;这样初始化后导致后面转移出错
              }
          }
      }
      for(LL i=1;i<=tot;i++){
          for(LL s=0;s<(1<<k);s++){
              dp[i+1][s]=max(dp[i+1][s],dp[i][s]);///当前这个点不匹配标记点
              for(LL j=0;j<trans[i].size();j++){
                      LL p=trans[i][j].first;
                      LL q=trans[i][j].second;
                      if( s>>(p-1) &1 ) continue;
                      if( s>>(q-1) &1 ) continue;
                      dp[i+1][s| (1<<(p-1) )| (1<<(q-1) ) ]=max( dp[i][s]+1, dp[i+1][ s |  ( 1<<(p-1) ) | (1<<(q-1) ) ]  );
              }
          }
      }
      LL ans=0;
      for(LL j=0;j<(1<<k);j++){
          ans=max(ans,dp[tot+1][j]);
      }
      cout<<ans<<"\n";
   }
   return 0;
}