P10339 [THUSC 2019] 补给计划

ImmatureDreamer · 2026-11-08 15:39:13 · 题解

写一道 Floyd 的题以纪念我故去的 S T2。

由于 N 较小，可以先使用 Floyd 预处理最短路，那么我们就需要用一些补给点覆盖全部的 K 个城市，问题就变成了怎么求出在某城市修建补给点能覆盖哪些受灾城市，以及怎么求最小的补给站数量。

若 u 到 v 的最短路经过点 x，则必有 \operatorname{dist}(u,v)=\operatorname{dist}(u,x)+\operatorname{dist}(x,v)，其中 \operatorname{dist} 是两点间最短路。故对于每个城市，枚举满足上述条件的城市，由于 K 只有 20 可以状压记录集合 s_i。

这样，问题就变成了每个城市都拥有一个集合，需要选尽量少的城市使得选中的并集为所有 K 个受灾城市。考虑 dp，定义 f_{i,S} 为考虑前 i 座城市，已经覆盖的受灾城市集合为 S 的最小补给站数量。可得转移：

• 若能修建，f_{i,S \operatorname{or} s_i} \leftarrow \min(f_{i,S \operatorname{or} s_i},f_{i-1,S})，其中 \operatorname{or} 为按位或。

答案即为 f_{N,2^K-1}。时间复杂度 \Theta(N^3+N \cdot 2^K)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=205,K=25;
const ll inf=0x7f7f7f7f7f7f7f7f;
int n,m,k,a[N],s[N],f[2][1<<21],t[N];
ll d[N][N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    memset(d,0x7f,sizeof d);
    for(int i=1;i<=n;++i) cin>>a[i],d[i][i]=0;
    for(int i=1;i<=k;++i) cin>>s[i];
    for(int i=1;i<=m;++i){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        d[u][v]=min(d[u][v],w);
        d[v][u]=min(d[v][u],w);
    }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(d[i][k]<inf&&d[k][j]<inf){
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
            }
        }
    }
    for(int i=1;i<=k;++i){
        for(int j=1;j<=n;++j){
            if(d[1][j]+d[j][s[i]]==d[1][s[i]]){
                t[j]|=(1<<(i-1));
            }
        }
    }
    memset(f[0],0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;++i){
        memset(f[i&1],0x3f,sizeof f[i&1]);
        for(int j=0;j<(1<<k);++j){
            f[i&1][j]=min(f[i&1][j],f[i&1^1][j]);
            if(a[i]) f[i&1][j|t[i]]=min(f[i&1][j|t[i]],f[i&1^1][j]+1);
        }
    }
    cout<<f[n&1][(1<<k)-1];
    return 0;
}