P4180 [BJWC2010] 严格次小生成树 题解

· · 题解

upd：修起来很容易的只要额外维护一树上并查集，权值变化后再复原不该删的边就行了。

题目传送门

冷兵器解法。无倍增，无树剖，无 LCT。

很遗憾，复杂度瓶颈在求最小生成树，仍为 \Theta(m\lg m)。

首先有结论：严格次小生成树和最小生成树只差一条边（如不理解该结论可参考其他题解，本文意在介绍后半部分的处理）。

所以先求出最小生成树，然后对于每一条非树边，如果删去这条边两个端点的路径上任意一边，显然都可以使用这条非树边代替。

所以每一条树边我们维护一个权值，表示能更新它的非树边的最小值。

这样一条条加入非树边，可以用树剖维护权值，但我们有一个更优的做法：

如果我们将边从小到大排序，后面的非树边不可能更新已被更新过的边，所以更新时考虑顺便把边删除。

可以使用并查集维护，每次修改时从两个点暴力往上跳，跳的时候如果一个点的并查集父亲还等于它自己，说明它和它树上父亲的边未被删除，此时更新这条边并统计答案，然后将这个点合并到它的树上父亲上。

统计答案的复杂度即为 \Theta(m\alpha(n))。

代码就放部分罢，有需要私信。

// 并查集函数
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
bool merge(int u,int v){return Find(u)!=Find(v)&&(f[f[u]]=f[v]);}
int main() {
    int n=read(),m=read();
    for (int i{1};i<=m;++i) {
        edge[i].u=read();
        edge[i].v=read();
        edge[i].w=read();
        edge[i].id=i;
    }
    sort(edge+1,edge+m+1);
    for (int i{1};i<=n;++i)
        f[i]=i;
    long long cnt{0};
    for (int i{1};i<=m;++i) {
        if (merge(edge[i].u,edge[i].v)) {
            cnt+=edge[i].w;edge[i].in=true;
            addE(edge[i].u,edge[i].v,i);
            addE(edge[i].v,edge[i].u,i);
        }
    }
    fz_init(1,1); // 处理了ID数组和fa数组
    for (int i{1};i<=n;++i) f[i]=i;
    long long ans=0x3f3f3f3f3f3f3f3f;
    for (int i{1};i<=m;++i) {
        if (!edge[i].in) {
            int u=Find(edge[i].u),v=Find(edge[i].v);
            while (u!=v) {
                if (dep[u]<dep[v]) swap(u,v);
                int e=ID[u]; // ID[u]: 点u与父亲之间边的编号
                if (edge[i].w>edge[e].w) ans=min(ans,edge[i].w-edge[e].w+cnt);
                u=f[u]=Find(fa[u]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}