最小生成树

发表于 更新于

一、常用模板

1、Kruskal

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
// https://www.luogu.com.cn/problem/P3366
using namespace std;
constexpr int maxn = 1000010;
int F[maxn];
int Find(int x){
    return x == F[x] ? x : F[x] = Find(F[x]);
}
struct E{
    int a, b, w;
    bool operator <(const E& e) const{
        return w < e.w;
    }
} edges[maxn];
int main(){
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; ++i) F[i] = i;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
    }
    sort(edges + 1, edges + 1 + m);
    long long int ans = 0;
    int cnt = 0;
    for(int i = 1; i <= m; ++i){
        int fa = Find(edges[i].a);
        int fb = Find(edges[i].b);
        if(fa ^ fb){
            ans += edges[i].w;
            F[fb] = fa;
            ++cnt;
            if(cnt == n - 1) break;
        }
    }
    if(cnt == n - 1) printf("%lld\n", ans);
    else printf("orz\n");
    return 0;
}

2、最小生成树的唯一性

对于 Kruskal 算法，只要计算为当前权值的边可以放几条，实际放了几条，如果这两个值不一样，那么就说明这几条边与之前的边产生了一个环（这个环中至少有两条当前权值的边，否则根据并查集，这条边是不能放的），即最小生成树不唯一。

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
// POJ-1679
using namespace std;
const int maxn = 1000010;
int F[maxn];
int Find(int x){
    return x == F[x] ? x : F[x] = Find(F[x]);
}
struct E{
    int a, b, w;
    bool operator <(const E& e) const{
        return w < e.w;
    }
} edges[maxn];
int solve(){
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; ++i) F[i] = i;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
    }
    sort(edges + 1, edges + 1 + m);
    long long int ans = 0;
    int cnt = 0, s1 = 0, s2 = 0, last = 0;
    bool flag = true;
    for(int i = 1; i <= m; ++i){
        if(i > last){
            if(s1 != s2){
                flag = false;
                break;
            }
            s2 = s1 = 0;
            for(int j = i; j <= m; ++j){
                if(edges[i].w == edges[j].w)
                    last = j, s1 += Find(edges[j].a) != Find(edges[j].b);
                else break;
            }
        }

        int fa = Find(edges[i].a);
        int fb = Find(edges[i].b);
        if(fa ^ fb){
            ans += edges[i].w;
            F[fb] = fa;
            ++cnt;
            ++s2;
        }
    }
    if(flag && s1 == s2) printf("%lld\n", ans);
    else printf("Not Unique!\n");
    return 0;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

3、次小生成树

非严格次小生成树
  • 求出无向图的最小生成树 $T$，设其权值和为 $M$
  • 遍历每条未被选中的边 $e = (u,v,w)$，找到 $T$ 中 $u$ 到 $v$ 路径上边权最大的一条边 $e’ = (s,t,w’)$，则在 $T$ 中以 $e$ 替换 $e’$，可得一棵权值和为 $M’ = M + w - w’$ 的生成树 $T’$.
  • 对所有替换得到的答案 $M’$ 取最小值即可
严格次小生成树

考虑刚才的非严格次小生成树求解过程，为什么求得的解是非严格的？

因为最小生成树保证生成树中 $u$ 到 $v$ 路径上的边权最大值一定 不大于 其他从 $u$ 到 $v$ 路径的边权最大值。换言之，当我们用于替换的边的权值与原生成树中被替换边的权值相等时，得到的次小生成树是非严格的。
解决的办法很自然：我们维护到 $2^i$ 级祖先路径上的最大边权的同时维护 严格次大边权，当用于替换的边的权值与原生成树中路径最大边权相等时，我们用严格次大值来替换即可。

这个过程可以用倍增求解，复杂度 $O(m \log m)$。

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
// 严格次小生成树
// https://www.luogu.com.cn/problem/P4180
using namespace std;
constexpr int maxn = 300100;
bool vis[maxn];
int F[maxn];

int Find(int x){
    return x ^ F[x] ? F[x] = Find(F[x]) : x;
}
struct E{
    int a, b, w;
    bool operator <(const E& e) const{
        return w < e.w;
    }
} roads[maxn];

struct Edge {
    int next, to, w;
} edges[maxn * 2];
int heads[maxn], pos = 0;
void addEdge(int a, int b, int w) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    edges[pos].w = w;
    heads[a] = pos;
}

template<int N>
struct T120B {
    int arr[N];
    int cnt = 0;
    T120B() {
        for (int i = 0; i < N; ++i) arr[i] = INT_MIN;
    }
    void add(int x) {
        int i = 0, j = N - 2;
        while (i < N && x <= arr[i]) ++i;
        if (i == N) return;
        while (j >= i) arr[j + 1] = arr[j], --j;
        arr[i] = x;
        if (cnt < N) ++cnt;
    }
};
int stp[maxn][20];
// max value
int stm[maxn][20];
// second-largest value
int sts[maxn][20];
int depth[maxn];

void dfs(int u, int fa){
    depth[u] = fa == -1 ? 0 : depth[fa] + 1;
    stp[u][0] = fa;
    for(int i = 1; ~stp[u][i-1] && i < 20; ++i){
        stp[u][i] = stp[stp[u][i-1]][i-1];
        T120B<4> max4;
        max4.add(sts[u][i-1]);
        max4.add(sts[stp[u][i-1]][i-1]);
        max4.add(stm[u][i-1]);
        max4.add(stm[stp[u][i-1]][i-1]);

        stm[u][i] = max4.arr[0];
        int sv = INT_MIN;
        for(int k = 1; k < 4; ++k){
            if(max4.arr[0] != max4.arr[k]){
                sv = max4.arr[k];
                break;
            }
        }
        sts[u][i] = sv;
    }
    for(int i = heads[u]; i; i = edges[i].next){
        int v = edges[i].to;
        if(fa == v) continue;
        stm[v][0] = edges[i].w;
        sts[v][0] = INT_MIN;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) return lca(v, u);
    for(int i = 19; ~i; --i){
        if(~stp[u][i] && depth[stp[u][i]] >= depth[v]) u = stp[u][i];
    }
    if(u == v) return u;
    for(int i = 19; ~i; --i){
        if(stp[u][i] != stp[v][i]) u = stp[u][i], v = stp[v][i];
    }
    return stp[u][0];
}
// 求u-v路径上不等于val的最大边
int query(int u, int v, int val){
    int res = INT_MIN;
    for(int i = 19; ~i; --i){
        if(~stp[u][i] && depth[stp[u][i]] >= depth[v]) {
            if(stm[u][i] == val)
                res = max(res, sts[u][i]);
            else
                res = max(res, stm[u][i]);
            u = stp[u][i];
        }
    }
    return res;
}

int main(){
    int n, m;
    //memset(vis, 0, sizeof(vis));
    //memset(heads, -1, sizeof(heads));
    pos = 0;
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; ++i) F[i] = i;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d", &roads[i].a, &roads[i].b, &roads[i].w);
    }
    sort(roads + 1, roads + 1 + m);
    long long int mst = 0, ans = 0;
    int cnt = 0;
    for(int i = 1; i <= m; ++i){
        int fa = Find(roads[i].a);
        int fb = Find(roads[i].b);
        if(fa ^ fb){
            //printf("select (%d %d %d)\n", roads[i].a, roads[i].b, roads[i].w);
            addEdge(roads[i].a, roads[i].b, roads[i].w);
            addEdge(roads[i].b, roads[i].a, roads[i].w);
            vis[i] = true;
            mst += roads[i].w;
            F[fb] = fa;
            ++cnt;
            if(cnt == n - 1) break;
        }
    }
    // 初始化
    sts[0][0] = INT_MIN;
    stm[0][0] = INT_MIN;
    sts[1][0] = INT_MIN;
    stm[1][0] = INT_MIN;
    // 如果调用dfs(1, 0) 需要初始化depth[0]
    depth[0] = -1;
    dfs(1, -1);
    ans = LONG_MAX;

    for(int i = 1; i <= m; ++i){
        if(vis[i]) continue;
        if(roads[i].a == roads[i].b) continue;
        int p = lca(roads[i].a, roads[i].b);

        int nw = max(query(roads[i].a, p, roads[i].w), query(roads[i].b, p, roads[i].w));
        //printf("lca(%d %d) = %d, nw = %d\n", roads[i].a, roads[i].b, p, nw);
        if(nw != INT_MIN)
            ans = min(ans, mst - nw + roads[i].w);
    }
    printf("%lld\n", ans);
    return 0;
}

4、Prim

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
// https://www.luogu.com.cn/problem/P3366
using namespace std;
constexpr int maxn = 1000010;
using ll = long long int;
struct Edge {
    int next, to, w;
} edges[maxn * 2];
int heads[maxn], pos = 0;

void addEdge(int a, int b, int w) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    edges[pos].w = w;
    heads[a] = pos;
}
bool vis[maxn];
int dist[maxn];
int main() {
    int n, m, a, b, w, cnt = 0;
    ll ans = 0;
    scanf("%d%d", &n, &m);
    memset(heads, -1, sizeof(heads));
    memset(vis, 0, sizeof(vis));
    memset(dist, 63, sizeof(dist));
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &a, &b, &w);
        addEdge(a, b, w);
        addEdge(b, a, w);
    }
    using pi = pair<int, int>;
    priority_queue<pi, vector<pi>, greater<>> q;
    q.emplace(0, 1);
    while (!q.empty()) {
        pi p = q.top(); q.pop();
        if (vis[p.second]) continue;
        vis[p.second] = true;
        ++cnt;
        ans += p.first;
        //printf("to %d val %d\n", p.second, p.first);
        if (cnt == n) break;
        for (int i = heads[p.second]; ~i; i = edges[i].next) {
            int v = edges[i].to;
            int nw = edges[i].w;
            if (!vis[v] && dist[v] > nw) q.emplace(dist[v] = nw, v);
        }
    
    }
    if (cnt == n) printf("%lld\n", ans);
    else printf("orz\n");
    return 0;
}