题解：P14362 [CSP-S 2025] 道路修复 / road（民间数据）

· · 题解

注意到 k 很小，考虑 2^k 枚举需要建的乡镇然后分别求 MST，但由于 m 过大会炸。

考虑往图上加一个乡镇对 MST 的贡献，发现可能参与新一轮 MST 的原边只有原图的 MST，这样就把每次 MST 的时间降到了 O(n \log n)。

使用类似状压 DP 转移的技巧，钦定最低位上的 1 为最后加的乡镇，转移 2^k 个 MST 的边即可。由于 kruskal 的特性，加入到 MST 中的边一定有序，所以可以线性地插入新边以避免排序。时间复杂度 O(m \log n + 2^k n\alpha(n))。

Code

#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
using namespace std;
const int N=1e4+20,M=1e6+10;
int n,m,k;
int c[20];
struct edge
{
    int u,v,w;
    bool operator <(const edge &x)const
    {
        return w<x.w;
    }
}e[M],a[20][N];
ll ans=inf,res[1<<10];
vector<edge>G[1<<10];

int fa[N],sz[N];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return;
    if(sz[x]<sz[y])swap(x,y);
    fa[y]=x;
    sz[x]+=sz[y];
    sz[y]=0;
}
signed main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[i]={u,v,w};
    }
    for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++)
    {
        if(find(e[i].u)==find(e[i].v))continue;
        merge(e[i].u,e[i].v);
        res[0]+=e[i].w;
        G[0].emplace_back(e[i]);
    }
    for(int i=1;i<=k;i++)
    {
        cin>>c[i];
        for(int j=1;j<=n;j++)cin>>a[i][j].w,a[i][j].u=j;
        sort(a[i]+1,a[i]+n+1);
    }
    ans=res[0];
    for(int i=1;i<(1<<k);i++)
    {
        for(int j=0;j<k;j++)
            if(i&(1<<j))res[i]+=c[j+1];
        int lb=(i&(-i));
        int x=log2(lb)+1,j=i^lb;
        m=0;
        int tot=1;
        for(auto y:G[j])
        {
            while(a[x][tot].w<=y.w&&tot<=n)e[++m]={a[x][tot].u,x+n,a[x][tot].w},tot++;
            e[++m]=y;
        }
    while(tot<=n)e[++m]={a[x][tot].u,x+n,a[x][tot].w},tot++;
        for(int s=1;s<=n+k;s++)fa[s]=s,sz[s]=1;
        sort(e+1,e+m+1);
        for(int s=1;s<=m;s++)
        {
            if(find(e[s].u)==find(e[s].v))continue;
            merge(e[s].u,e[s].v);
            res[i]+=e[s].w;
            G[i].emplace_back(e[s]);
        }
        ans=min(ans,res[i]);

    }
    cout<<ans<<"\n";
    return 0;
}