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
|
#include <algorithm>
const int MAXN = 10005;
const int MAXM = 20005;
struct {
int u, v, w, type;
Edge() {}
Edge(int u, int v, int w, int type) : u(u), v(v), w(w), type(type) {}
bool operator<(const Edge &another) const {
return w < another.w;
}
} E[MAXM << 1];
struct UnionFindSet {
int fa[MAXN];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
fa[q] = p;
}
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
} ufs;
int main() {
int n, k, m;
scanf("%d %d %d", &n, &k, &m);
m--;
int cnt = 0;
for (int i = 0; i < m; i++) {
int u, v, w1, w2;
scanf("%d %d %d %d", &u, &v, &w1, &w2);
E[cnt++] = Edge(u, v, w1, 1);
E[cnt++] = Edge(u, v, w2, 2);
}
m = cnt;
std::sort(E, E + m);
int ans = 0;
ufs.init(n);
for (int i = 0; i < m; i++) {
if (E[i].type == 1 && ufs.find(E[i].u) != ufs.find(E[i].v)) {
ufs.merge(E[i].u, E[i].v);
ans = std::max(ans, E[i].w);
n--;
if (!--k) break;
}
}
for (int i = 0; i < m; i++) {
if (ufs.find(E[i].u) != ufs.find(E[i].v)) {
ufs.merge(E[i].u, E[i].v);
ans = std::max(ans, E[i].w);
if (--n == 1) break;
}
}
printf("%dn", ans);
return 0;
}
|
近期评论