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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510, M = 10010;
int n, m;
struct Edge{
int a, b, w;
bool f;
bool operator < (const Edge& t) const{
return w < t.w;
}
}edges[M];
int p[N];
int dist[2][N][N];
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int find(int x){
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
void dfs(int u, int f, int mx1, int mx2, int d1[], int d2[]){
d1[u] = mx1, d2[u] = mx2;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j != f){
int t1 = mx1, t2 = mx2;
if(w[i] > t1) t2 = t1, t1 = w[i];
else if(w[i] < t1 && w[i] > t2) t2 = w[i];
dfs(j, u, t1, t2, d1, d2);
}
}
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof(h));
for(int i = 0; i < m; i++){
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
sort(edges, edges + m);
for(int i = 1; i <= n; i++) p[i] = i;
LL sum = 0;
for(int i = 0; i < m; i++){
int a = edges[i].a , b = edges[i].b, w = edges[i].w;
int pa = find(a), pb = find(b);
if(pa != pb){
p[pa] = pb;
sum += w;
add(a, b, w);
add(b, a, w);
edges[i].f = true;
}
}
for(int i = 1; i <= n; i++) dfs(i, -1, -1e9, -1e9, dist[0][i], dist[1][i]);
LL res = 1e18;
for(int i = 0; i < m; i++){
if(!edges[i].f){
int a = edges[i].a , b = edges[i].b, w = edges[i].w;
LL t;
if(w > dist[0][a][b])
t = sum + w - dist[0][a][b];
else if(w > dist[1][a][b])
t = sum + w - dist[1][a][b];
res = min(res, t);
}
}
cout << res << endl;
return 0;
}
|
