P11260

2021CHD · 2025-10-31 19:48:45 · 题解

题目大意

有 n 个点，m 条边的无向图，其中有 k 条边为关键边，其余 m-k 条边为非关键边，保证非关键边能够把 n 个点连通。

请对于每个 0\sim k 中的 i 求解：在 m 条边中选择若干条边使得图连通，并且恰好选了 i 条关键边的最小边权和。

题解

首先需要注意到关键边不一定不成环，所以我们得到的不一定是一个生成树，也有可能有一些仅由关键边围成的环。

接下来，让我们考虑一个贪心做法：我们先求出 k=0 时的最小生成树，然后考虑每次加入一条能使答案变得最小的一条关键边。

具体地，枚举一条未被加入过的关键边，将其两个端点在生成树上的路径取出，如果路径上不全为关键边，可以选择一条边权最大的非关键边删掉并将此边加入生成树，否则这条边即使被选上也不会加入生成树。

直接暴力（连树上倍增都不需要）做，用 Kruskal 算法求解最小生成树可以做到 O(nk^2+m\log m)，时间复杂度已经完全可以接受。

参考代码

这是我的 AC 记录。

:::success[参考代码]

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long i,j,n,m,k,u[1100000],v[1100000],w[1100000],ok[1100000],num[1100000],*mp[11000],*mpv[11000],fa[11000],fv[11000],f[11000],deep[11000],fl[100],ans[100],det,wh,tt;
long long root(long long a)
{
    if(f[a]==0)
    return a;
    else
    return f[a]=root(f[a]);
}
bool in(long long a,long long b)
{
    a=root(a);
    b=root(b);
    if(a==b)
    return false;
    f[a]=b;
    return true;
}
void make_tree()
{
    long long i;
    for(i=1;i<=n;i++)
    num[i]=0;
    for(i=1;i<=m;i++)
    if(ok[i]==1)
    {
        num[u[i]]++;
        num[v[i]]++;
    }
    for(i=1;i<=n;i++)
    {
        mp[i]=new long long[num[i]+1];
        mpv[i]=new long long[num[i]+1];
        mp[i][0]=0;
    }
    for(i=1;i<=m;i++)
    if(ok[i]==1)
    {
        mp[u[i]][0]++;
        mp[u[i]][mp[u[i]][0]]=v[i];
        mpv[u[i]][mp[u[i]][0]]=i;
        mp[v[i]][0]++;
        mp[v[i]][mp[v[i]][0]]=u[i];
        mpv[v[i]][mp[v[i]][0]]=i;
    }
}
void delete_tree()
{
    long long i;
    for(i=1;i<=n;i++)
    {
        delete [] mp[i];
        delete [] mpv[i];
    }
}
void dfs(long long x)
{
    long long i;
    deep[x]=deep[fa[x]]+1;
    for(i=1;i<=mp[x][0];i++)
    if(mp[x][i]!=fa[x])
    {
        fa[mp[x][i]]=x;
        fv[mp[x][i]]=mpv[x][i];
        dfs(mp[x][i]);
    }
}
long long get(long long x,long long y)
{
    long long s=0;
    while(x!=y)
    if(deep[x]>=deep[y])
    {
        if(w[fv[x]]>s)
        s=w[fv[x]];
        x=fa[x];
    }
    else
    {
        if(w[fv[y]]>s)
        s=w[fv[y]];
        y=fa[y];
    }
    return s;
}
void del(long long x,long long y)
{
    long long s=-1,ww=0;
    while(x!=y)
    if(deep[x]>=deep[y])
    {
        if(w[fv[x]]>s)
        {
            s=w[fv[x]];
            ww=fv[x];
        }
        x=fa[x];
    }
    else
    {
        if(w[fv[y]]>s)
        {
            s=w[fv[y]];
            ww=fv[y];
        }
        y=fa[y];
    }
    ok[ww]=0;
}
main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(i=1;i<=m;i++)
    scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);
    for(i=1;i<=m-k;i++)
    num[i]=i+k;
    sort(num+1,num+m-k+1,[](long long a,long long b)->bool{return w[a]<w[b]||w[a]==w[b]&&a<b;});
    for(i=1;i<=m-k;i++)
    if(in(u[num[i]],v[num[i]]))
    {
        ans[0]=ans[0]+w[num[i]];
        ok[num[i]]=1;
    }
    for(i=1;i<=k;i++)
    {
        make_tree();
        dfs(1);
        det=1000000001;
        wh=0;
        for(j=1;j<=k;j++)
        if(fl[j]==0)
        {
            tt=w[j]-get(u[j],v[j]);
            if(tt<det)
            {
                det=tt;
                wh=j; 
            }
        }
        ans[i]=ans[i-1]+det;
        del(u[wh],v[wh]);
        ok[wh]=1;
        fl[wh]=1;
        w[wh]=0;
        delete_tree();
    }
    for(i=0;i<=k;i++)
    printf("%lld\n",ans[i]);
}

:::

好像少了点什么？

正确性证明去哪里了？

为了证明上述贪心做法的正确性，我们引入本题的 wqs 二分做法。

wqs 二分

首先我们需要使得答案是一颗生成树，于是我们需要把关键边连出的每个连通块都先求一次最小生成树，不在最小生成树上的关键边一定不会出现在生成树中。

这是因为，如果不在最小生成树上的关键边出现在了生成树，那么就说明这条关键边两端点在最小生成树上的路径不全在生成树上，因为树上不会有环。

根据最小生成树的性质，这条关键边两端点在最小生成树上的路径中的每条边权值都不大于这条边，并且我们一定可以找到一条路径上的边来代替这条关键边使得我们的生成树的权值和最小，所以不在最小生成树上的关键边不可能出现在生成树中。

于是将不在最小生成树上的关键边最后考虑，现在我们的关键边不成环，答案就一定是一棵生成树。

考虑将每条关键边的权值增加 w，令 w 在 -\infty 到 +\infty 之间变化。

:::warning[提示] 这里出现的 \infty（包括下面出现的所有 \infty）严格意义上来说都不是指真正的无穷，而只是代指一个很大的数，比如说对于本题，10^9 就已经足够大了。 :::

观察我们在最小生成树中选择的关键边，不难发现，如果在 w 取某一个值的时候我们的最小生成树中选择了恰好 x 条关键边，那么这一时刻求出的最小生成树一定是原图选择恰好 x 条关键边前提下的最小生成树。

因为如果原图中还有边权和更小的选择恰好 x 条关键边的生成树，那么在每条关键边的权值都增加了 w 以后，就可以得到一个 w 取那一个值情形下更小的生成树，这显然是不可能的。

我们注意到一点，w 越小，我们选的关键边就越多。于是我们可以二分一个 w，直到我们选择了恰好 x 条关键边，我们就可以求出原问题中 i=x 的解了。

我们只要对于每个 i 分别二分就可以得出答案。

如果你真的要写这个做法，有几个细节需要注意：

1. 可以在忽略关键边的前提下先求出最小生成树，只保留在最小生成树上的非关键边，可以把边数从 O(m) 条压缩到 O(n) 条（这里认为我们 O(k)<O(n)）。这样复杂度才会是 O(nk\log V)，才可以过。
2. 答案可能是非完全凸的，也就是说，可能有一些 i 二分不出答案，使用各种方式都可以处理此问题。（比如在最后再将线性变化的数值填入答案数组中）
3. 记得把不在最小生成树上的关键边加入答案，显然这些关键边可以将边权从小到大排序，然后就只需要执行两个凸包的合并。

代码没写。

好像又少了点什么？

正确性证明又去哪里了？（而且这个做法乍看之下也和上面的贪心没有联系）

接下来我们来证明 wqs 二分是对的。

证明

一般情况下，我们只需要证明答案是凸的（比如在本题中，只需证明答案关于关键边边数 i 是下凸的），就可以证明 wqs 二分的正确性。

但是当你真的试图开始证明答案是凸的，你很可能会遇到麻烦，于是我们考虑放弃定式思维。我们可以直接证明 wqs 二分是对的，通过 wqs 二分的正确性反推出答案的凸性。（因为最后合并生成树上的关键边和不在生成树上的关键边时也要用到答案的凸性，所以还是需要证明答案是凸的）

考虑 w=-\infty 时，显然所有关键边都会被选，而当 w=+\infty 时，显然所有关键边都不会被选。

现在我们考虑将 w 从 +\infty 逐渐减小至 -\infty 的过程中我们对关键边的选择。

首先在这里插入一个引理：字典序最小的生成树是最小生成树，并且最小生成树（按边权排序后）是字典序最小的生成树，这里的字典序是按照边权为唯一关键字排序的。粗略的证明就是 Kruskal 算法，因为 Kruskal 算法求出的会是一个字典序最小的生成树。

:::info[更严格的证明]

细心的人可能已经发现：Kruskal 算法能求出字典序最小的生成树，但是这里的“字典序”是按照边权为第一关键字，和一个随机顺序（比如边的编号）为第二关键字排序的，并非按照边权为唯一关键字排序的。

所以我们放弃考虑 Kruskal 算法，去寻找一个更有效的数学建模。

我们考虑用拟阵进行建模。别被吓跑了，接下来我会说人话的。

我们实际上就是需要在一个连通图上选出一些边，使得这些边不形成环。如果我们选择了尽可能多的边，那么就可以得到一个最小生成树。

我们依次检查拟阵的三个性质：

1. 空集合法，这是显然的。
2. 在一个合法的集合中选取一个子集仍然合法，这也是显然的。
3. 对于一个合法的集合 A 和一个合法的集合 B，如果集合 A 的大小大于集合 B 的大小，那么一定存在一个元素 s 属于 A，使得 s 不属于 B，并且把 s 加入 B 以后得到的新集合仍然合法，这并不是很显然，所以我们接下来考虑先证明此性质。

考虑一个无环的边集 A 和无环的边集 B，如果 A 的边数多于 B 的边数，考虑考察边集 B 把整个图划分为的连通块。

不难发现 A 中至多只有 B 的大小条边可以在同一个连通块内，否则必然会出现环。又由于 A 的边数多于 B 的边数，所以 A 中至少有一条边跨过了 B 中的两个连通块，把这条边加入 B 就可以使得新边集仍无环。

于是我们成功将问题建模成了拟阵，对于拟阵模型，有一个经典结论：字典序最小的极大合法集合是所有极大合法集合中总和最小的，所有极大合法集合中总和最小（按权值排序后）就是字典序最小的极大合法集合。（极大合法集合就是不为任意一个合法集合的真子集的合法集合）

要证明这个经典结论，需要先证明所有极大合法集合的元素个数相同。

这点比较容易，设 A 和 B 是两个极大合法集合，并且 A 的大小大于 B，那么根据性质，在 A 中可以选出一个元素加入 B 使得新集合仍合法，那么明显 B 就不是极大的。

于是接下来取字典序最小的极大合法集合为 A，如果最优解不为 A，而为 B，于是 B 的总和比 A 的总和小，于是将 A 和 B 排序后至少有一个对应位置 x 使得 A_x>B_x。

考虑取出 A 的前 x-1 个元素组成集合 A'，再取出 B 的前 x 个元素组成集合 B'，由于 B' 的大小比 A' 大，所以我们可以在 B' 中找到一个元素 z 加入 A' 后使得新集合 S 仍合法。由于此时必定有 z<A_x，所以 S 的字典序小于 A，向 S 中不断添加单个元素，直到 S 是极大的，此时我们就找到了一个字典序比 A 更小的极大合法集合 S，显然与假设矛盾。

所以除了字典序最小的极大合法集合，其他的极大合法集合权值都不可能最小，所以字典序最小的极大合法集合权值就是最小的。

我们就成功证明了上述结论。

:::

有了这个结论，我们就可以不去观察生成树的边权和而是去观察生成树的字典序。

考虑我们正要选上第一条关键边的时刻，此时我们正要全责一条关键边 p，在最小生成树上取出权值与 p 相同的非关键边集合 Q。

考虑将 w 增加 \epsilon，我们就不能选 p 了。

这只能是因为 Q 被选上了，所以 Q 中一定有一条边 q 连接了 p 两个端点所在的连通块，所以我们选了 p 就不能选 q。（更严格的证明可以通过上面折叠框中的性质三得到）

于是我们把 q 替换为 p 以后实际上没有影响当前连通块的形态，所以后面的方案不会产生任何变更。

我们发现实际上不只有第一条关键边加入时的情形是这样，每条关键边加入时都是类似的。

值得注意的是，在同一个时刻，可能有多条关键边同时加入，因为这些边之间互相独立，我们可以控制这些边部分加入来得到想要的关键边数，因为此时关键边和对应被替换的非关键边权值相同。

所以 wqs 二分是有效的，因为我们二分的序列是单调的，也就是可二分的。又由于 wqs 二分只能在答案凸的时候有效，所以我们的答案也只能是凸的。

现在，wqs 二分的正确性证完了，然后呢？

贪心的正确性去哪里了？

其实我们上面已经证过了：将 w 从 +\infty 逐渐减小至 -\infty 的过程中，我们每次都用一条关键边替换了一条非关键边，而从不反悔，这简直和我们的贪心流程一模一样。

唯一的区别在于贪心时我们也考虑了不在生成树上的边，由于答案是凸的，我们实际上就是在贪心的过程中做了凸包的合并，这也是对的。

所以贪心的正确性也就证完了。

::::success[Bonus：关于时间复杂度的优化]{open}

首先需要注意，这一部分专注于理论复杂度的优化，我并没有实际去写代码。

如果有人得出了比我更优的复杂度也欢迎在评论区踢我。

以下默认所有关键边都在生成树上，可以用最小生成树算法快速剔除不在生成树上的关键边，并用凸包合并将两部分的答案合并起来，这些的复杂度都不会超过 O(k\log k)，不会成为复杂度瓶颈的一部分。

:::warning[提示]

以下分析复杂度时默认 O(k)\le O(n)。

你也可以理解为我们在复杂度里写的 k 实际上都是 \min(n,k)。

:::

（图片上展示的是本题另一篇题解的第一条评论）

我们要做到优于这个复杂度，也就是要优于 O(k^2+n\alpha(n)+m)。（这里的复杂度是期望的复杂度）

首先观察我们的暴力贪心的复杂度：O(nk^2+m\log m)。

首先很容易发现一个瓶颈：我们在最开始需要求解一次最小生成树。

常见的算法的复杂度都超过了我们要求的复杂度：Kruskal 算法即便使用基数排序，复杂度也只能达到 O(m\alpha(n))；而 Prim 算法则受限于优先队列的复杂度，只能达到 O(n\log n+m)；Boruvka 算法的复杂度更是 O(m\log n)，难以优化。

是时候使用科技了：我们可以使用随机化线性时间最小生成树算法，也就是 KKT 算法，论文贴在这里，感兴趣的人可以去了解一下。在本文中，我们不会详细介绍 KKT 算法的算法流程和复杂度证明等，我们只把这个算法当做黑盒来用。

一些你需要知道的信息：KKT 算法的空间复杂度为 O(m)，期望时间复杂度也为 O(m)，并且有高达 1-e^{\Omega(m)} 的概率会以 O(m) 的时间运行。

我们直接把 KKT 用到暴力贪心上，于是得到期望复杂度为 O(nk^2+m) 的贪心，现在考虑优化贪心部分的复杂度。

很明显，我们每次需要断一条边，加一条边并保证图还是一棵数，查询两点间边权的最大值，这明显就是动态树问题，直接用 LCT 就可以把期望复杂度做到 O(k^2\log n+m)。

现在怎么才能继续优化呢？考虑到动态树问题非常困难，我们考虑此题中动态树问题的特殊性质。

我们发现，我们的问题无法离线下来做，因为每次加哪条边，删哪条边只有做完了当前需要做的查询操作才能得知。但是经过观察，我们可以求出我们所有操作中需要删除的边集。

考虑将所有的关键边的边权都设为 0，跑一遍最小生成树，那么所有 k 条关键边都会出现在最小生成树上。

考虑将关键边全部去除，再将剩余的 n-1-k 条在最小生成树上的非关键边的边权设为 0，再跑一遍最小生成树（可以证明此时的生成树是原图忽略关键边以后的最小生成树，证明方式和上面类似），那么我们就会多选进来 k 条非关键边。这 k 条非关键边就是我们整个过程中需要删除的边。

考虑到我们只会删除在查找过程中能找到的边权最大的边，于是我们可以把除了这 k 条非关键边以外的边全部缩起来，我们的树的大小就从 O(n) 变成了 O(k)。缩点的过程略微精细实现一下就可以做到 O(n)，所以这一部分不是复杂度的瓶颈。

接下来需要冷静思考，不要想歪然后试图去解决经典问题。

:::error[想歪了的后果]

这一部分是无法将复杂度优化达标的。

我们容易发现此题中，我们一共需要 O(k) 次删边加边操作和 O(k^2) 次查询操作，于是考虑一次删边加边就相当于改变了一次树的形态，我们就可以考虑暴力做删边加边。

接下来我们需要解决一个经典问题：查询树上路径最大值，允许离线。

在我的认知范围内，如果 n,q 同阶，我无法得出一个比 O(n\log\log n) 的复杂度更优的做法。于是我们的复杂度至多只能优化到期望 O(k^2\log\log k+m)，离目标复杂度还是差了一个 \log\log。

关于 O(n\log\log n) 的做法，我不想在这里展开。我相信这个做法应该很典，大家应该都知道。

Update：

fydj 得出了复杂度为 O(n\alpha(n)) 的做法，具体细节可以去看他的文章。

然而这样做以后期望复杂度为 O(k^2\alpha(k)+m)，离目标复杂度还是差了一个 \alpha。

:::

我们考虑使用 Kruskal 重构树来进行树上路径权值的最大值。

首先一开始我们需要先花费不超过 O(k\log k) 的时间跑一遍 Kruskal 并建出 Kruskal 重构树，这一部分不是复杂度的瓶颈。

接下来对于每一次删边加边操作，其实就是将树上的两个点之间的权值最大的边删除，然后再在两个点之间连接一条权为 0 的边（其实就相当于把这两个点直接缩成一个点了）。反映到 Kruskal 重构树上的变化就是将两个点到到它们的最近公共祖先中间的所有儿子按照权值进行合并。不难发现这是一个将两个有序数组合成一个有序数组的过程，容易用一轮归并排序做到线性。

我们知道，两点之间路径的权值最大值就是 Kruskal 重构树上两点最近公共祖先的权值，问题转化为线性预处理，常数时间求解两点的最近公共祖先。

这是一个经典问题，容易将其转化为树的欧拉序上的 RMQ 问题，并使用加减 1RMQ（或基于状压的线性 RMQ 算法）达成目标。

由于我们只有 O(k) 次删边加边操作，每次需要 O(k)，以及 O(k^2) 次查询操作，每次需要 O(1)，于是这一部分的复杂度就被顺利优化至 O(k^2)。

最后总的期望时间复杂度就是 O(k^2+m)，达成目标。

这个做法的空间复杂度为 O(m)。

::::

:::info[后记]

「人の正義もどうせ人の数だけあるんだろう」

秘密

:::