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

发表于 分类于 本文字数： 700 阅读时长 ≈ 2 分钟

true
严格次小生成树
BJWC 2010
省选/NOI-
#9d3dcf
  • Luogu P4180
  • BZOJ #1977

概述

对于这种求次小生成树的题目，我们可以用一种统一的方法来解决：

  1. 求出来整张图的最小生成树，时间复杂度 $O(m \log m)$；
  2. 对于不在最小生成树上的每一条边，枚举能够替换的最大的边，时间复杂度 $O(m \log n)$。

证明

为了严谨，我们在这里证明一下最小生成树和次小生成树可以只差一条边。

首先，我们需要知道为什么Kruskal算法是对的。

在Kruskal算法中，我们贪心地从小到大选取每一条边，然后尝试将其加到生成树中。
那么，如果一条边 $(u,v)$ 能够不出现在最小生成树上，那么其边权肯定大于等于当前生成森林中 $u$ 到 $v$ 的这一条路径上边权的最大值，否则我们完全可以用这条边替换掉该路径上的某一条边权更大的边来得到一个更优的答案。

这样的话，如果我们得到的次小生成树与最小生成树相差的边不止一条，那么我们完全可以选择这几条边里面的任意一条，换回最小生成树里面的一条对应的边，最终得到的结果是完全不会劣于当前结果的。

因此，我们得到的次小生成树完全可以与最小生成树只差一条边。

具体做法

我们可以枚举差的这一条边，放到树上查询两端点之间的边权最大值，记录一下两者的差值，最后取最小值即可。

当然，我们会遇到两者相等的情况，此时我们替换之后得到的就是非严格最小生成树，需要找边权更小的一条边。

此时我们不只需要查询两端点之间的边权最大值，同时还要查询次大值。
边权再小的边就不需要记录了，如果这条边与次大值相同，我们完全可以拿它把最大值给替换了，得到一个更小的生成树。

那么直接树剖之后线段树维护即可。

实现

代码如下：

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010, M = 600010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int fa[N], son[N], dep[N], sz[N], top[N];
int dfn[N], id[N], nw[N], tot;
int tmpw[N];
void dfs1(int p, int fa, int depth)
{
    ::fa[p] = fa, dep[p] = depth, sz[p] = 1;
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa)continue;
        dfs1(e[i], p, depth + 1);
        tmpw[e[i]] = w[i];
        sz[p] += sz[e[i]];
        if(sz[e[i]] > sz[son[p]])son[p] = e[i];
    }
}
void dfs2(int p, int t)
{
    dfn[p] = ++tot, id[tot] = p, nw[tot] = tmpw[p], top[p] = t;
    if(!son[p])return;
    dfs2(son[p], t);
    for(int i = h[p]; ~i; i = ne[i])
    {
        if(e[i] == fa[p] || e[i] == son[p])continue;
        dfs2(e[i], e[i]);
    }
}
struct SegTree
{
    int l, r;
    int maxn, maxs;
};
SegTree tr[N << 3];
pair<int, int> merge(pair<int, int>lhs, pair<int, int>rhs)
{
    pair<int, int>res;
    if(lhs.first > rhs.first)
    {
        res.first = lhs.first;
        res.second = max(lhs.second, rhs.first);
    }
    else if(lhs.first < rhs.first)
    {
        res.first = rhs.first;
        res.second = max(rhs.second, lhs.first);
    }
    else
    {
        res.first = lhs.first;
        res.second = max(lhs.second, rhs.second);
    }
    return res;
}
void pushup(int p)
{
    pair<int, int>res = merge(make_pair(tr[p << 1].maxn, tr[p << 1].maxs),
        make_pair(tr[p << 1 | 1].maxn, tr[p << 1 | 1].maxs));
    tr[p].maxn = res.first;
    tr[p].maxs = res.second;
}
void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    if(l == r)
    {
        tr[p].maxn = nw[l];
        tr[p].maxs = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}
pair<int, int> segmax(int p, int l, int r)
{
    if(tr[p].l >= l && tr[p].r <= r)return make_pair(tr[p].maxn, tr[p].maxs);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(r <= mid)return segmax(p << 1, l, r);
    else if(l > mid)return segmax(p << 1 | 1, l, r);
    else return merge(segmax(p << 1, l, r), segmax(p << 1 | 1, l, r));
}
pair<int, int> maxpath(int p, int q)
{
    pair<int, int>res = make_pair(-1, -1);
    while(top[p] != top[q])
    {
        if(dep[top[p]] < dep[top[q]])swap(p, q);
        res = merge(res, segmax(1, dfn[top[p]], dfn[p]));
        p = fa[top[p]];
    }
    if(dep[p] < dep[q])swap(p, q);
    if(p != q)res = merge(res, segmax(1, dfn[q] + 1, dfn[p]));
    return res;
}
struct Edge
{
    int u, v, w;
    bool operator < (const Edge &rhs)const
    {
        return w < rhs.w;
    }
};
Edge edge[M];
bool vis[M];
struct DSU
{
    int fa[N];
    void init(int n)
    {
        for(int i = 1; i <= n; i++)
            fa[i] = i;
    }
    int find(int x)
    {
        if(fa[x] != x)fa[x] = find(fa[x]);
        return fa[x];
    }
    bool soyuz(int u, int v)
    {
        int fu = find(u), fv = find(v);
        if(fu != fv)
        {
            fa[fv] = fu;
            return true;
        }
        else return false;
    }
};
DSU dsu;
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    dsu.init(n);
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge[i] = { u,v,w };
    }
    sort(edge + 1, edge + 1 + m);
    int cnt = n;
    ll ans = 0;
    for(int i = 1; i <= m; i++)
    {
        int u = edge[i].u, v = edge[i].v;
        if(!dsu.soyuz(u, v))continue;
        int w = edge[i].w;
        ans += w;
        cnt--;
        add(u, v, w), add(v, u, w);
        vis[i] = true;
        if(cnt == 1)break;
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    build(1, 1, n);
    int res = 1e9;
    for(int i = 1; i <= m; i++)
    {
        if(vis[i])continue;
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if(u == v)continue;
        pair<int, int>k = maxpath(u, v);
        if(w != k.first)res = min(res, w - k.first);
        else if(k.second != -1)res = min(res, w - k.second);
    }
    printf("%lld\n", ans + res);
    return 0;
}