题解：CF2021E2 Digital Village (Hard Version)

· · 题解

前言

写这句话是为了不让我的题解没有前言。

题意

给一个边有边权的无向图，有给定的 k 点需要网络，选择一些点装服务器之后，需要网络的点会连向延迟最小的服务器，延迟定义为路径上的最大边权，求装了 x 台服务器的情况下最小的延迟和。

Solution

看到这个“路径上的最大边权”，想都不想跑一个最小生成树，显然需要网络的点会走树上的路径。

考虑从小到大加入最小生成树的边，每次会合并两个连通块，我们尝试合并它们的答案，设 dp_{u,i} 表示 u 所在连通块使用 i 个服务器的最小延迟和。

枚举两个连通块的服务器数，设为 i,j。

如果两者都不为 0，那么连通它们的边显然不会走（从小到大加边，两个连通块里的边绝对更小），没有贡献。

如果其中一个为 0，那么这个连通块里的所有需要网络的点（记作 sz_u）都会从这条边到对面去，产生 sz_u\times w 的贡献。

于是发现合并两个连通块复杂度为 O(sz_u\times sz_v)，全部合并起来复杂度为 O(n^2)，证明同树上背包复杂度证明，可以通过 E2。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 5080
int T,n,m,k,i,j,sz[N],fa[N],x,res[N];
int dp[N][N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int u,v,w;
vector<pair<int,pair<int,int> > > e;
#define fi first
#define se second
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        for(i=1;i<=n;i++) fa[i]=i;
        for(i=1;i<=k;i++) cin>>x,sz[x]=1;
        for(i=1;i<=m;i++) cin>>u>>v>>w,e.push_back({w,{u,v}});
        sort(e.begin(),e.end());
        for(auto x:e)
        {
            u=x.se.fi,v=x.se.se,w=x.fi;
            int fu=find(u),fv=find(v);
            if(fu==fv) continue;
            fa[fv]=fu;
            for(i=1;i<=sz[fu]+sz[fv];i++) res[i]=1e18;
            for(i=1;i<=sz[fu];i++) res[i]=min(res[i],dp[fu][i]+w*sz[fv]);
            for(i=1;i<=sz[fv];i++) res[i]=min(res[i],dp[fv][i]+w*sz[fu]);
            for(i=1;i<=sz[fu];i++)
                for(j=1;j<=sz[fv];j++) res[i+j]=min(res[i+j],dp[fu][i]+dp[fv][j]);
            for(i=1;i<=sz[fu]+sz[fv];i++) dp[fu][i]=res[i];
            sz[fu]+=sz[fv];
        }
        int rt=find(1);
        for(i=1;i<=n;i++) cout<<dp[rt][i]<<" ";
        cout<<endl;
        for(i=0;i<=n;i++)
        {
            sz[i]=0,fa[i]=0,res[i]=0;
            for(j=0;j<=n;j++) dp[i][j]=0;
        }
        e.clear();
    }
    return 0;
 }

The End.