【题解】P2323 [HNOI2006]公路修建问题

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

有一座岛上有\(n\)个景点，从\(1-n\)编号，现在需要修公路将这些景点连接起来，可以修一级或二级的公路，一级公路的花费大于二级公路。

现在要修\(n−1\)条公路将景点连接，且在这\(n−1\)条公路中有\(k\)条是一级公路。

现给出\(n,k\)以及可以修的景点对和修一级公路和二级公路的花费。求满足要求的最小花费。

\(1\le n \le 10000, k\le n−1,m\le 30000\)

分析

首先，按照一级公路为代价Kruskal，建\(k\)个边；然后按照二级公路为代价，继续加到\(n-1\)条边。

实现

\(100pts,138ms,2.84mb\)

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
#include<bits/stdc++.h>

using namespace std;
int n, k, m;
int ans;

int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int fa[100005];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

int merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) fa[x] = y;
}

struct node {
    int a, b, c1, c2, id, lev;
} e[20005];

bool cmp1(node a, node b) {
    return a.c1 < b.c1;
}

bool cmp2(node a, node b) {
    return a.c2 < b.c2;
}

bool cmp3(node a, node b) {
    return a.id < b.id;
}

node anss[200005];
int tot;
bool book[200005];

int main() {
    n = read();
    k = read();
    m = read();
    for (int i = 1; i < m; i++) {
        e[i].a = read();
        e[i].b = read();
        e[i].c1 = read();
        e[i].c2 = read();
        e[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(e + 1, e + m, cmp1);
    int sum = 0;
    for (int i = 1; i < m; i++) {
        if (find(e[i].a) != find(e[i].b)) {
            merge(e[i].a, e[i].b);
            ans = max(ans, e[i].c1);
            e[i].lev = 1;
            anss[++tot] = e[i];
            book[e[i].id] = true;
            sum++;
        }
        if (sum == k) break;
    }
    sum = 0;
    sort(e + 1, e + m, cmp2);
    for (int i = 1; i < m; i++) {
        if (book[e[i].id]) continue;
        if (find(e[i].a) != find(e[i].b)) {
            ans = max(ans, e[i].c2);
            merge(e[i].a, e[i].b);
            e[i].lev = 2;
            anss[++tot] = e[i];
            sum++;
        }
        if (sum == n - k - 1) break;
    }
    cout << ans << endl;
    sort(anss + 1, anss + tot + 1, cmp3);
    for (int i = 1; i <= tot; i++) {
        cout << anss[i].id << " " << anss[i].lev << endl;
    }

    return 0;
}