P4180 【模板】严格次小生成树[BJWC2010]

传送门

可以考虑先做这道题：CF609E Minimum spanning tree for each edge

这道题和上面本质是相同的。

考虑先把这张图的最小生成树建出来，然后改动一条边，形成次小生成树。

$Q.$ 怎么证明次小生成树是最小生成树改动一条边形成的？

$A.$ 先考虑一下我们 $Kruskal$ 建最小生成树的做法，我们把所有边按照边权排序，然后从小到大依次取，如果出现环则放弃。

首先，还是按照 $Kruskal$ 的做法，把边排序（标成蓝色的代表选择，灰色代表原来的）。

考虑反证法（口胡版证明）：

既然我们要证明次小生成树是最小生成树改动一条边形成的，那么我们就要证明改动两条边的情况总是可以少改动一条边，而形成一个边权小于等于改动两条边情况下生成树的生成树。

引理：一条边往前跳，补上前面的空是不行的。

按照 $Kruskal$ 算法，我们发现前面留空是有它的理由的，因为前面加边的话会形成环，破坏树的性质，而 $Kruscal$ 是从左到右依次加边的，所以后面位置的变动并不会影响它变成一个环。

再考虑移动两条边的情况：

移动两条边，只有一起向前移动，一起向后移动，一条向前，一条向后的情况。

假设你把两条边向前移动，根据上面的引理，容易证明不行。

假设你就是想把前面留出空来，让后面的边可以插进去，也就是一条向前，一条向后的情况，也就是这样：

发现没有，其实这样是更优的：

可以这么理解：前面标红色部分和后面的边是独立存在的，就是说，红色部分的形态不管怎么变，后面连边和前面形成一个环，就是形成了环，后面连边不形成环，就是不形成环。

假设我们的次小生成树是把两条边往后跳

根据刚才我们的说法，我们把一条前面的边插入前面的空，而不是插进末尾绝对不是最优的，如图：

（注意这是特别指移动两条边的情况，如果只移动一条边这还是要考虑的）

所以，我们只能把两条边都移动到末尾（否则只要有一条边插进前面的空，都可以构造出更优解），如图：

等等！为什么要移动两条边，移动一条边不是更优吗？

所以，证毕！

$Q.$ 怎么实现呢？

$A.$ 考虑到题目要求的是严格次小生成树，根据刚才的引理，我们只需要改动一条边，就可以得到次大生成树。

不妨不从改动的角度想，而是从加入一条边，删掉一条边的角度考虑。

在最小生成树上面加入一条边，路径上面一定存在一个环，那么我们要把环上的一条边删掉，根据贪心的想法，我们要删掉环上面边权最大的一条边。

但是这时，严格两字有出来烦人了，如果你删掉的最大值就是你加进的那条边的权值，那么得到的生成树大小就和最小生成树相等了。

于是，我们退而求其次，如果最大值就是加进的边，那么我们使用严格次大值。

我们记录 $anc[u][i]$ ，表示 $u$ 的 $2^i$ 辈祖先， $Max1[u][i]$ ，表示 $u$ 到它的 $2^i$ 辈祖先的路径上面最大值， $Max2[u][i]$ ，表示 $u$ 到它的 $2^i$ 辈祖先路径上面严格次大值。

转移十分简单

$Max1[u][i-1]==Max1[anc[u][i-1]][i-1]$ 时，我们只能在两个次大值里面选，即 $Max2[u][i]=max(Max2[u][i-1],Max2[anc[u][i-1]][i-1])$

$Max1[u][i-1]>Max1[anc[u][i-1]][i-1]$ 时，说明 $Max1[anc[u][i-1]][i-1]$ 有成为次大值的可能，即， $Max2[u][i]=max(Max2[u][i-1],Max1[anc[u][i-1]][i-1])$

剩下一种情况也是类似，不再赘述。

注意：要开 $\text{long long}$ ，最大值 $\rm INF$ 开大一点

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 23
#define EDGE 300005
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int anc[MAXN][MAXM],Max1[MAXN][MAXM],Max2[MAXN][MAXM];
//最大值和严格次大值
//Max1[u][i]表示u到u的2^i辈祖先之间边的最大值
//Max2[u][i]表示.....的严格次大值
int n,m;
struct Edge{
    int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
    G[u].push_back(Edge{v,w});
}

//--------------------Kruscal
struct Edge1{
    int u,v,w;
}e[EDGE];
inline bool operator < (const Edge1 &A,const Edge1 &B){
    return A.w<B.w;
}
namespace BCJ{
    int fa[MAXN];
    inline void Init_BCJ(){
        for (register int i=0;i<MAXN;++i) fa[i]=i;
    }
    int Fa(int i){
        return fa[i]==i?i:fa[i]=Fa(fa[i]);
    }
}
using namespace BCJ;
int MST[EDGE];//是否出现在最小生成树中
inline int Kruscal(){
    Init_BCJ();
    sort(e+1,e+1+m);
    int mst=0;
    for (register int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        int fau=Fa(u),fav=Fa(v);
        if (fau!=fav){
            fa[fau]=fav;
            mst+=w;
            MST[i]=true;
            AddEdge(u,v,w);
            AddEdge(v,u,w);
        }
    }
    return mst;
}
//----------------------------
int dep[MAXN];
void dfs(int u,int father){
    anc[u][0]=father;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i].to,w=G[u][i].len;
        if (v!=father){
            Max1[v][0]=w;
            Max2[v][0]=-INF;//不存在次大值
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
}
inline void Merge(int &max1,int &max2,int max1d,int max1u,int max2d,int max2u){
    max1=max(max1d,max1u);
    if (max1d>max1u) max2=max(max2d,max1u);
    else if (max1d==max1u) max2=max(max2d,max2u);
    else max2=max(max1d,max2u);
}
inline void Init(){
    for (register int i=1;i<MAXM;++i){
        for (register int u=1;u<=n;++u){
            anc[u][i]=anc[anc[u][i-1]][i-1];
            Merge(Max1[u][i],Max2[u][i],Max1[u][i-1],Max1[anc[u][i-1]][i-1],Max2[u][i-1],Max2[anc[u][i-1]][i-1]);
        }
    }
}
inline int LCA(int u,int v){
    if (u==1||v==1) return 1;
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]){
            u=anc[u][i];
        }
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]){
            u=anc[u][i],v=anc[v][i];
        }
    }
    return anc[u][0];
}
inline int Hop(int u,int lca,int val){
    int maxn=-INF;//次大值!=val
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[lca]){//I can H♂p
            if (Max1[u][i]!=val) maxn=max(maxn,Max1[u][i]);//这样可以采用最大值
            else maxn=max(maxn,Max2[u][i]);//不能采用最大值，要不然就不是严格次大生成树了，所以只能采用严格次大值
            u=anc[u][i];
        }
    }
    return maxn;
}
#undef int
int main(){
#define int long long
    n=read(),m=read();
    for (register int i=1;i<=m;++i){
        e[i].u=read();e[i].v=read();e[i].w=read();
    }
    int mst=Kruscal();
    dfs(1,1);
    Init();
    int ans=INF;
    for (register int i=1;i<=m;++i){
        if (!MST[i]){
            int u=e[i].u,v=e[i].v,w=e[i].w;
            int lca=LCA(u,v);
            int len=max(Hop(u,lca,w),Hop(v,lca,w));
            ans=min(ans,mst+w-len);//减去len这条边，加上w这条边
        }
    }
    printf("%lld\n",ans);
}

这道题应该树剖也能做，但是大材小用了，而且不好调试。

Steven_Meng's Blog

P4180 【模板】严格次小生成树[BJWC2010]

下一篇：P2898 [USACO08JAN]haybale猜测Haybale Guessing