题目链接
题目大意
给你n个宝石，有m对(a[i],b[i])关系，以及k种必须出现的宝石
你要保证出现k种必须出现的宝石(每种宝石>=1即可)，且出现的宝石要满足m对关系的两两相邻
求最少的宝石数，不满足则直接输出-1
\(1<=n<=1e5\;\;0<=m<=1e5\;\;1<=k<=17\)
题目思路
首先相邻则可以当作建边
然后用bfs预处理这k的点的两两直接的距离
然后用状压dp转移
\(dp[sta][last]\) 表示当前状态为sta，且现在在last点
用状压最朴素的转移即可
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=3e5+5,inf=0x3f3f3f3f,mod=998244353;
const int eps=1e-6;
int n,m,k;
int head[maxn],cnt;
int c[maxn];
int dis[20][20],len[maxn];
int dp[1<<17][20];
struct edge{
int to,next;
}e[maxn<<1];
void add(int u,int v){
e[++cnt]={v,head[u]};
head[u]=cnt;
}
void bfs(int x){
memset(len,0x3f,sizeof(len));
len[x]=0;
queue<int> que;
que.push(x);
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=head[x];i;i=e[i].next){
if(len[e[i].to]!=inf) continue;
len[e[i].to]=len[x]+1;
que.push(e[i].to);
}
}
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",&c[i]);
}
for(int i=1;i<=k;i++){
bfs(c[i]);
for(int j=1;j<=k;j++){
dis[i][j]=len[c[j]];
}
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=k;i++){ //预处理
dp[1<<(i-1)][i]=1;
}
for(int sta=0;sta<(1<<k);sta++){
for(int last=1;last<=k;last++){
if(!(sta&(1<<(last-1)))||dp[sta][last]==inf) continue; //没有交集
for(int nxt=1;nxt<=k;nxt++){
if(sta&(1<<(nxt-1))) continue; //已经有交集了
dp[sta|(1<<(nxt-1))][nxt]=min(dp[sta|(1<<(nxt-1))][nxt],dp[sta][last]+dis[last][nxt]);
}
}
}
int ans=inf;
for(int i=1;i<=k;i++){
ans=min(ans,dp[(1<<k)-1][i]);
}
if(ans==inf) ans=-1;
printf("%d\n",ans);
return 0;
}