题解：P10339 [THUSC 2019] 补给计划

WorldMachine · 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]);
}