抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

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

发布于：2019年8月3日

传送门

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所以，证毕！

Q.Q. 怎么实现呢？

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

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

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

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

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

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

转移十分简单

Max1[u][i−1]==Max1[anc[u][i−1]][i−1]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])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[u][i-1]>Max1[anc[u][i-1]][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])Max2[u][i]=max(Max2[u][i-1],Max1[anc[u][i-1]][i-1])

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#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);
}

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

相关文章
LibreOJ NOIP Round 1 DNA 序列 字符串哈希AT1219 歴史の研究AT3621 Small MultipleBZOJ 1195 [HNOI2006]最短母串基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/bf23f83d.html

更新于：2022年6月14日

题解

树上倍增

评论