题面

大秦为你打开题目传送门

题目描述

小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：($value(e)$ 表示边 $e$ 的权值) $\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)$。

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数。

接下来 $M$ 行，每行 $3$ 个数 $x,y,z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 6
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6

样例输出 #1

1
11

提示

数据中无向图不保证无自环。

对于 $50%$ 的数据， $N\le 2000$，$M\le 3000$。

对于 $80%$ 的数据， $N\le 5\times 10^4$，$M\le 10^5$。

对于 $100%$ 的数据， $N\le 10^5$，$M\le 3\times10^5$，边权 $\in [0,10^9]$，数据保证必定存在严格次小生成树。

思路

首先找出最小生成树，然后加一条边，再删掉这个环里面除了刚刚加进去的边中最大的即可，别忘了严格次小。

代码

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
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
    inline void read(char *s) {
        scanf("%s", s + 1);
    }
};
using namespace FastIO;

const int N = 100010;
const int M = 300010;

int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

struct Edge {
    int to, nt, wt;
    Edge() {}
    Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[M << 1];
int hd[N], cnte;
inline void AddEdge(int u, int v, int w) {
    e[++cnte] = Edge(v, hd[u], w);
    hd[u] = cnte;
}

int n, m;

struct Side {
    int u, v, w, flag;
}side[M];

int vis[N];
int dep[N], fat[N][20];
pair<ll , ll >st[N][20];

inline void Input() {
    read(n, m);
    int u, v, w;
    for(int i = 1; i <= m; i++) {
        read(u, v, w);
        side[i].u = u, side[i].v = v, side[i].w = w, side[i].flag = 0;
    }
}

inline ll Kruscal() {
    ll ans = 0;
    for(int i = 1; i <= m; i++) {
        int u = find(side[i].u), v = find(side[i].v);
        if(u == v) continue;
        AddEdge(side[i].u, side[i].v, side[i].w);
        AddEdge(side[i].v, side[i].u, side[i].w);
        fa[u] = v;
        side[i].flag = 1;
        ans += side[i].w;
    }
    return ans;
}

pair<ll , ll >merge(pair<ll , ll >u, pair<ll , ll >v) {
    pair<ll , ll >ans = make_pair(0, 0);
    if(u.first < v.first) swap(u, v);
    ans.first = u.first;
    if(v.first == u.first) {
        ans.second = max(u.second, v.second);
    }
    else ans.second = max(v.first, u.second);
    return ans;
}

pair<ll , ll >find(int u, int v) {
    pair<ll , ll >ans = make_pair(0, 0);
    for(int i = 19; i >= 0; i--) {
        if(dep[fat[u][i]] >= dep[v]) {
            ans = merge(ans, st[u][i]);
            u = fat[u][i];
        }
    }
    return ans;
}   

inline void Dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    fat[u][0] = f;
    for(int i = 1; i < 20; i++) {
        fat[u][i] = fat[fat[u][i - 1]][i - 1];
        st[u][i] = merge(st[u][i - 1], st[fat[u][i - 1]][i - 1]);
    }
    for(int i = hd[u]; i; i = e[i].nt) {
        int v = e[i].to;
        if(v == f) continue;
        st[v][0] = make_pair(e[i].wt, 0);
        Dfs(v, u);
    }
}

inline int LCA(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i--) {
        if(dep[fat[u][i]] >= dep[v]) {
            u = fat[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(fat[u][i] != fat[v][i]) {
            u = fat[u][i], v = fat[v][i];
        }
    }
    return fat[u][0];
}

inline void Work() {
    for(int i = 1; i <= n; i++) fa[i] = i;
    sort(side + 1, side + m + 1, [](Side a, Side b) {
        return a.w < b.w;
    });
    ll mst = Kruscal();
    ll ans = 1e18;
    // cout << mst << endl;
    Dfs(1, 0);
    for(int i = 1; i <= m; i++) {
        if(side[i].flag == 1) continue;
        int lca = LCA(side[i].u, side[i].v);
        pair<long long , long long >now = merge(find(side[i].u, lca), find(side[i].v, lca));
        if(now.first != side[i].w) {
            ans = min(ans, mst + side[i].w - now.first);
        }else{
            ans = min(ans, mst + side[i].w - now.second);
        }
    }
    printf("%lld", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}