\(\large\text{CodeForces1741G-Kirill and Company题解}\)

题面传送门（有翻译（由黄巨佬提供））

思路

预处理

因为 \(k\) 很小，所以可以先 bfs 预处理出家在 \(i(2\le i\le n)\) 的人能捎带上哪些集合的人，在表示集合时用一个 \(0\) 到 \(2^k-1\) 的整数 \(j\) 表示，若 \(j\) 在二进质下的从小到大第 \(l\) 位是 \(1\)，那么这个集合就包含第 \(l\) 的没车的人。

在 bfs 从 \(i\) 转移到 \(j\) 时，如果 \(i\) 能成为 \(1\) 到 \(j\) 的最短路上的点，那么家在 \(i\) 的人能捎带上的人的集合家在 \(j\) 的人也能捎带上，注意集合里还要加上家在 \(j\) 点且没车的人。

预处理完后做 dp ：

• 设 \(dp_{i,j}\) 表示前 \(i\) 个人是否能捎带上 \(j\) 集合里的所有人。
• 转移（扩散型）：
  • 如果第 \(i+1\) 个人没车，那么如果 \(dp_{i,j}=1\) 则 \(dp_{i+1,j}=1\) 否则 \(dp_{i+1,j}=0\) 。
  • 如果第 \(i+1\) 个人有车，那么如果 \(dp_{i,j}=1\) 且第 \(i+1\) 个人回家的路上能捎带上集合 \(l\) 的人，则对于 \(j\) 和 \(l\) 的并集 \(q\)，\(dp_{i+1,q}=1\)。
• 在表示集合的时候，可以用预处理时的方法，那么 \(j\) 和 \(l\) 的并集就是 \(j|l\)。

答案

对于每个 \(dp_{tot,j}=1\) 的 \(j\)，输出集合大小最大的 \(j\) 的集合大小。

时间复杂度

对于每个测试点

bfs

\(O(m\cdot 2^k)\)

dp

\(O(tot\cdot 2^{2k})\)

总

\(O(m\cdot 2^k+tot\cdot 2^{2k})\)

空间复杂度

\(O(n\cdot 2^k+tot\cdot 2^k)\)

代码（不建议在做出来之前看）

优美的码风

#include <bits/stdc++.h>

using namespace std;

const int kMaxN=1e4+1,kMaxS=1<<6;

int t,n,m,p[kMaxN],o,h[kMaxN],k,c[kMaxN],dp[kMaxN][kMaxS],ma;
bool a[kMaxN][kMaxS],f[kMaxN];
vector<int>b[kMaxN];
queue<int>q;

void R(int x,int l,int j){
	if(j<=c[x]){
		if(j<c[x]){
			c[x]=j;
			q.push(x);
		}
		for(int i=0;i<(1<<k);i++){
			a[x][(i|p[x])]|=a[l][i];
		}
	}
}

int S(int x){
	int ans=0;
	for(;x;ans++,x-=(x&(-x))){
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	for(cin>>t;t--;){
		cin>>n>>m;
		for(int i=1,u,v;i<=m;i++){
			cin>>u>>v;
			b[u].push_back(v),b[v].push_back(u);
		}
		cin>>o;
		for(int i=1;i<=o;i++){
			cin>>h[i];
		}
		cin>>k;
		fill(p+1,p+n+1,0);
		fill(f+1,f+o+1,0);
		for(int i=1,a;i<=k;i++){
			cin>>a;
			f[a]=1;
			p[h[a]]+=(1<<(i-1));
		}
		fill(a[1],a[n]+kMaxS,0);
		a[1][0]=1;
		fill(c+1,c+n+1,n+1);
		for(R(1,0,0);q.size();q.pop()){
			for(int i:b[q.front()]){
				R(i,q.front(),c[q.front()]+1);
			}
		}
		fill(dp[0],dp[o]+kMaxS,0);
		dp[0][0]=1;
		for(int i=0;i<o;i++){
			for(int j=0;j<(1<<k);j++){
				if(dp[i][j]){
					if(!f[i+1]){
						for(int l=0;l<(1<<k);l++){
							if(a[h[i+1]][l]){
								dp[i+1][j|l]=1;
							}
						}
					}else{
						dp[i+1][j]=1;
					}
				}
			}
		}
		ma=0;
		for(int i=0;i<(1<<k);i++){
			ma=max(ma,S(i)*dp[o][i]);
		}
		cout<<k-ma<<"\n";
		for(int i=1;i<=n;i++){
			b[i].clear();
		}
	}
	return 0;
}