题解：CF2041N Railway Construction

PizzaYY · 2026-05-13 19:58:04 · 题解

前言

人类智慧题。

思路

下文中均认为按权值排序时，权值相同时编号小的更小。

先考虑如何在可接受的范围内求出最小生成树，由于图接近完全图，所以想到 Boruvka 算法。

我们可以先迭代一次，即每个点向权值最小且能连的那个点连一条边。可以发现，连通块个数是 O(\sqrt m) 的，证明如下：

两个连通块 i,j 之间没有边的必要条件为连通块 i 内权值最小的点和连通块 j 内权值最小的点无边。

每两个连通块都至少需要删掉一个边，而删掉边的个数为 m，所以连通块的量级为 O(\sqrt m)。

求一个点 x 能连的最小边是简单的，先把与 x 有关的那些删掉的边取出来，并按另一个端点的权值排序。设得到的序列为 g_x。此时我们可以暴力按权值从小到大的顺序枚举 y，维护一个指针 p，若 y=g_{x,p}，则让 p+1 且枚举下一个 y。否则 (x,y) 一定能连。这部分是均摊 O(n+m) 的。

接下来考虑如何把这 O(\sqrt m) 个连通块进一步合并。

考虑 Prim，若我们知道了任意两个连通块之间能连的最小的边，即可在 O((\sqrt m)^2+m)=O(m) 的复杂度内求出最终的生成树。

设第 i,j 个连通块之间被删掉的边构成的集合为 E_{i,j}，我们只需要取第 i 个集合中权值前 |E_{i,j}|+1 个点，用上面的方法求出这些点连向连通块 j 中最小的点。由于 |E_{i,j}| 之和为 m，所以复杂度能分析到 O(m)。

::::info[如果你被卡常了]

设枚举第 i 个联通块的点为 x，第 j 个的为 y，若 a_x+a_y 比之前求出来的最小值要大，可以直接换一个 x。

::::

此时我们就以 O(n+m) 的复杂度求出了最小生成树。

考虑删掉一个点过后怎么求。

对于最小生成树上的叶子节点，我们显然不需要再求一次，直接输出原来的最小生成树边权和减去叶子节点唯一连出去的一条边的权值。这条边是比较好记录的。

然后我们发现，最小生成树上的非叶节点只有 O(\sqrt m) 个，证明如下：

对于一个非叶节点 x，必须存在一个 y 使得 y 能连的最小边端点为 x。

此时排序后在 x 前面的就必须和这个 y 断掉。则非叶节点最多的情况肯定是取到一个前缀，这个前缀最长就是 O(\sqrt m)。

所以我们只需要对删除非叶节点后重新跑一边暴力，复杂度为 O((n+m)\sqrt m)。注意无解的情况需要特判。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5,B = 1005,inf = 2e18;
int n,m,a[N],id[N],U[N],V[N],ss[N];
inline bool cmp(int x,int y){return a[x]!=a[y]?a[x]<a[y]:x<y;}
int f[N],id2[N],du[N],sum[N];
bool vis[N];
struct node{
    int u,v,w;
    inline friend bool operator < (node x,node y)
    {
        return x.w<y.w;
    }
}w[B][B],mn[B];
vector<int> vec[N],g[N],tmp[N];
vector<pair<int,int>> e[B][B];
inline int find(int x)
{
    if(f[x]==x) return x;
    return f[x] = find(f[x]);
}
inline int work(int ban = 0)
{
    for(int i = 1;i<=n;i++) f[i] = i;
    int res = 0;
    for(int i = 1;i<=n;i++)
    {
        if(i==ban) continue;
        int p = 0;
        for(int j = 1;j<=n;j++)
        {
            if(id[j]==i||id[j]==ban)
            {
                if(p<g[i].size()&&g[i][p]==id[j]) p++;
                continue;
            }
            if(p<g[i].size()&&g[i][p]==id[j])
            {
                p++;
                continue;
            }
            if(find(i)!=find(id[j]))
            {
                f[find(i)] = find(id[j]);
                res+=a[i]+a[id[j]];
                if(!ban) du[i]++,du[id[j]]++,sum[i]+=a[i]+a[id[j]],sum[id[j]]+=a[i]+a[id[j]];
            }
            break;
        }
    }
    int cnt = 0;
    for(int i = 1;i<=n;i++)
        if(i!=ban&&find(i)==i) id2[i] = ++cnt;
    for(int i = 1;i<=cnt;i++)
    {
        vec[i].clear();
        for(int j = 1;j<=cnt;j++)
            e[i][j].clear();
    }
    for(int i = 1;i<=n;i++)
        if(id[i]!=ban) vec[id2[find(id[i])]].push_back(id[i]);
    for(int i = 1;i<=n;i++)
    {
        if(i==ban) continue;
        for(auto j:g[i])
            if(j!=ban) e[id2[find(i)]][id2[find(j)]].push_back({i,j});
    }
    for(int i = 1;i<=cnt;i++)
        for(int j = i+1;j<=cnt;j++)
        {
            w[i][j] = {0,0,inf};
            for(auto _:e[i][j]) tmp[_.first].push_back(_.second);
            for(int k = 0;k<min(vec[i].size(),e[i][j].size()+1);k++)
            {
                int x = vec[i][k],p = 0;
                for(auto y:vec[j])
                {
                    if(a[x]+a[y]>=w[i][j].w) break;
                    if(p<tmp[x].size()&&tmp[x][p]==y)
                    {
                        p++;
                        continue;
                    }
                    w[i][j] = min(w[i][j],{x,y,a[x]+a[y]});
                    break;
                }
            }
            w[j][i] = w[i][j];
            for(auto _:e[i][j]) tmp[_.first].clear();
        }
    for(int i = 1;i<=cnt;i++) mn[i] = w[1][i],vis[i] = 0;
    while(1)
    {
        int u = 0;
        for(int i = 2;i<=cnt;i++)
            if(!vis[i]&&(u==0||mn[i]<mn[u])&&mn[i].w<inf) u = i;
        if(!u) break;
        vis[u] = 1;
        res+=mn[u].w;
        if(!ban) du[mn[u].u]++,du[mn[u].v]++,sum[mn[u].u]+=mn[u].w,sum[mn[u].v]+=mn[u].w;
        for(int i = 2;i<=cnt;i++)
            if(!vis[i]) mn[i] = min(mn[i],w[u][i]);
    }
    for(int i = 2;i<=cnt;i++)
        if(!vis[i]) return -1;
    return res;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
        cin>>a[i],id[i] = i;
    for(int i = 1;i<=m;i++)
        cin>>U[i]>>V[i],g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]),ss[U[i]]++,ss[V[i]]++;
    sort(id+1,id+n+1,cmp);
    for(int i = 1;i<=n;i++) sort(g[i].begin(),g[i].end(),cmp);
    int tmp = work();
    if(tmp==-1)
    {
        if(n==2) cout<<"0\n0";
        else
        {
            int p = 1;
            for(int i = 1;i<=n;i++)
                if(ss[i]==n-1) p = i;
            int res = work(p);
            for(int i = 1;i<=n;i++)
                if(i==p) cout<<res<<' ';
                else cout<<"-1 ";
        }
        return 0;
    }
    for(int i = 1;i<=n;i++)
        if(du[i]==1) cout<<tmp-sum[i]<<' ';
        else cout<<work(i)<<' ';
    return 0;
}