自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 22:57:04，当前版本为作者最后更新于2024-04-30 18:19:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛出了这题，我是这样趋势的：

• 打了状压 DP 之后过了大样例；
• 旁边的大佬说会有重边，于是判了重边；
• 但是我没保存文件……哈哈

言归正传，这题还是比较简单的，只要注意到 $K\leq 20$ 这神奇的数据范围，然后就很容易想到 $\mathcal O(2^KN)$ 的状压 DP 做法：首先，对于每个受灾点，处理出每个点是否可能在它到 $1$ 的最短路上，然后状压所有状态即可：对于每个状态，枚举每个可以建立救助站的点，看这个点在哪些点的最短路图中（不用真正地建图），然后答案就是去掉这些被覆盖点后状态的答案 $+1$。

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
typedef long long ll;
const int N = 205, M = 10005;
int n, m, k, v2[N], dp[1048580];
bool v1[N];
ll dis[N][N];
int G1[N];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1, x; i <= n; i++) scanf("%d", &x), v1[i] = x;
	for (int i = 1, x; i <= k; i++) scanf("%d", &x), v2[i] = x;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1, u, v, w; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		dis[u][v] = min(dis[u][v], (ll)w);
		dis[v][u] = min(dis[v][u], (ll)w);
	}
	for (int i = 1; i <= n; i++) dis[i][i] = 0;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) G1[j] |= ((dis[v2[i]][1] == dis[v2[i]][j] + dis[j][1]) << i - 1);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int c = 1; c < (1 << k); c++) {
		for (int i = 1; i <= n; i++) {
			if (!v1[i]) continue;
			dp[c] = min(dp[c], dp[c ^ (G1[i] & c)] + 1);
		}
	}
	printf("%d\n", dp[(1 << k) - 1]);
}