【BZOJ1196】公路修建问题

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1196

看起来和免费道路那道题是有共同点的，但细细一想，其实二者并不一样。免费道路要求恰好有k条鹅卵石路，而本题要求至少k条一级道路。

本题是想让边权最大的边最小（别去想最小生成树的性质！！！），所以可以二分答案，因为必然最大边权越大越容易满足，任意一条边都可以成为一级道路。

我们毕竟是要验证答案，所以应该先加一遍一级道路，然后再去补二级道路，这样才能够保证符合条件的不被判断为不符合条件。

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 inline int get_num() {
 7     int num = 0;
 8     char c = getchar();
 9     while (c < '0' || c > '9') c = getchar();
10     while (c >= '0' && c <= '9')
11         num = num * 10 + c - '0', c = getchar();
12     return num;
13 }
14 
15 const int maxn = 1e4 + 5, maxm = 2e4 + 5;
16 
17 struct Edge {
18     int u, v, w1, w2;
19 } edge[maxm];
20 
21 int n, k, m, maxw, fa[maxn];
22 
23 int dj_find(int i) {
24     if (fa[i] == i) return i;
25     else return fa[i] = dj_find(fa[i]);
26 }
27 
28 inline void dj_merge(int a, int b) {
29     fa[dj_find(a)] = dj_find(b);
30 }
31 
32 inline int check(int x) {
33     int cnt = 0;
34     for (int i = 1; i <= n; ++i) fa[i] = i;
35     for (int i = 1; i <= m - 1; ++i) {
36         if (edge[i].w1 > x) continue;
37         int u = edge[i].u, v = edge[i].v;
38         if (dj_find(u) != dj_find(v)) {
39             dj_merge(u, v);
40             ++cnt;
41         }
42     }
43     if (cnt < k) return 0;
44     for (int i = 1; i <= m - 1; ++i) {
45         if (edge[i].w2 > x) continue;
46         int u = edge[i].u, v = edge[i].v;
47         if (dj_find(u) != dj_find(v)) {
48             dj_merge(u, v);
49             ++cnt;
50         }
51     }
52     if (cnt != n - 1) return 0;
53     else return 1;
54 }
55 
56 int main() {
57     n = get_num(), k = get_num(), m = get_num();
58     for (int i = 1; i <= m - 1; ++i) {
59         edge[i].u = get_num(), edge[i].v = get_num();
60         edge[i].w1 = get_num(), edge[i].w2 = get_num();
61         maxw = max(maxw, edge[i].w1);
62     }
63     int l = 1, r = maxw;
64     while (l < r) {
65         int mid = l + (r - l) / 2;
66         if (check(mid)) r = mid;
67         else l = mid + 1;
68     }
69     printf("%d", l);
70     return 0;
71 }

AC代码（BZOJ、二分）

然而，做完一道题，刷新世界观。。。

本着骗一下AC量的原则，我把相同的代码交到了洛谷上，，，结果，呵呵呵。。。

一看，哦输出格式变了。我就稍微一改，死活过不去，用Special Judge评，老是说我图没连通。那我快去看看题解吧。

居然，还可以用贪心做！那我改去学学贪心好了。。。

参照Kruskal算法的做法，我们先按c1从小到大排一下序，然后从里面条k条，肯定刚好k条最好；然后选择二级道路肯定会更好些，所以我们再按照c2排序，挑完剩下的。

注意，并不保证最小的c1大于最大的c2；若c1相同则按c2从大到小排序，因为这样可以保证后面最优。

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 inline int get_num() {
 7     int num = 0;
 8     char c = getchar();
 9     while (c < '0' || c > '9') c = getchar();
10     while (c >= '0' && c <= '9')
11         num = num * 10 + c - '0', c = getchar();
12     return num;
13 }
14 
15 const int maxn = 1e4 + 5, maxm = 2e4 + 5;
16 
17 struct Edge {
18     int id, u, v, w1, w2;
19 } edge[maxm];
20 
21 bool comp1(const Edge& lhs, const Edge& rhs) {
22     if (lhs.w1 == rhs.w1) return lhs.w2 > rhs.w2;
23     else return lhs.w1 < rhs.w1;
24 } //w1相等，则留w2小的，之后会更优
25 
26 bool comp2(const Edge& lhs, const Edge& rhs) {
27     return lhs.w2 < rhs.w2;
28 }
29 
30 int fa[maxn];
31 
32 int dj_find(int i) {
33     if (fa[i] == i) return i;
34     else return fa[i] = dj_find(fa[i]);
35 }
36 
37 inline void dj_merge(int a, int b) {
38     fa[dj_find(a)] = dj_find(b);
39 }
40 
41 struct Ans {
42     int id, type;
43     bool operator < (const Ans& rhs) const {
44         return id < rhs.id;
45     }
46 } ans[maxn];
47 
48 int main() {
49     int n = get_num(), k = get_num(), m = get_num();
50     int cnt = 0, me = 0, aeid = 0;
51     for (int i = 1; i <= m - 1; ++i) {
52         edge[i].id = i;
53         edge[i].u = get_num(), edge[i].v = get_num();
54         edge[i].w1 = get_num(), edge[i].w2 = get_num();
55     }
56     sort(edge + 1, edge + m, comp1);
57     for (int i = 1; i <= n; ++i) fa[i] = i;
58     for (int i = 1; i <= m - 1; ++i) {
59         int u = edge[i].u, v = edge[i].v;
60         if (dj_find(u) != dj_find(v)) {
61             dj_merge(u, v);
62             me = max(me, edge[i].w1);
63             ans[++aeid].id = edge[i].id, ans[aeid].type = 1;
64             if (++cnt == k) break;
65         }
66     }
67     sort(edge + 1, edge + m, comp2);
68     for (int i = 1; i <= m - 1; ++i) {
69         int u = edge[i].u, v = edge[i].v;
70         if (dj_find(u) != dj_find(v)) {
71             dj_merge(u, v);
72             me = max(me, edge[i].w2);
73             ans[++aeid].id = edge[i].id, ans[aeid].type = 2;
74         }
75     }
76     printf("%d
", me);
77     sort(ans + 1, ans + n);
78     for (int i = 1; i <= n - 1; ++i)
79         printf("%d %d
", ans[i].id, ans[i].type);
80     return 0;
81 }

AC代码（洛谷、贪心）

当然，并不是说二分不能做，二分也可以，是我写错了而已。

我以为跑完二分，顺便记录每一次的答案即可，但显然不对，因为你不知道最后一次是对的还是错的，所以我们需要在求出答案之后，再建一次树。

  1 #include <cstdio>
  2 #include <algorithm>
  3 
  4 using namespace std;
  5 
  6 inline int get_num() {
  7     int num = 0;
  8     char c = getchar();
  9     while (c < '0' || c > '9') c = getchar();
 10     while (c >= '0' && c <= '9')
 11         num = num * 10 + c - '0', c = getchar();
 12     return num;
 13 }
 14 
 15 const int maxn = 1e4 + 5, maxm = 2e4 + 5;
 16 
 17 struct Edge {
 18     int u, v, w1, w2;
 19 } edge[maxm];
 20 
 21 int n, k, m, maxw, fa[maxn];
 22 
 23 int dj_find(int i) {
 24     if (fa[i] == i) return i;
 25     else return fa[i] = dj_find(fa[i]);
 26 }
 27 
 28 inline void dj_merge(int a, int b) {
 29     fa[dj_find(a)] = dj_find(b);
 30 }
 31 
 32 struct Ans {
 33     int id, type;
 34     bool operator < (const Ans& rhs) const {
 35         return id < rhs.id;
 36     }
 37 } ans[maxn];
 38 
 39 inline int check(int x) {
 40     int cnt = 0;
 41     for (int i = 1; i <= n; ++i) fa[i] = i;
 42     for (int i = 1; i <= m - 1; ++i) {
 43         if (edge[i].w1 > x) continue;
 44         int u = edge[i].u, v = edge[i].v;
 45         if (dj_find(u) != dj_find(v)) {
 46             dj_merge(u, v);
 47             ++cnt;
 48         }
 49     }
 50     if (cnt < k) return 0;
 51     for (int i = 1; i <= m - 1; ++i) {
 52         if (edge[i].w2 > x) continue;
 53         int u = edge[i].u, v = edge[i].v;
 54         if (dj_find(u) != dj_find(v)) {
 55             dj_merge(u, v);
 56             ++cnt;
 57         }
 58     }
 59     if (cnt != n - 1) return 0;
 60     else return 1;
 61 }
 62 
 63 inline void build(int x) {
 64     int cnt = 0;
 65     for (int i = 1; i <= n; ++i) fa[i] = i;
 66     for (int i = 1; i <= m - 1; ++i) {
 67         if (edge[i].w1 > x) continue;
 68         int u = edge[i].u, v = edge[i].v;
 69         if (dj_find(u) != dj_find(v)) {
 70             dj_merge(u, v);
 71             ans[++cnt].id = i, ans[cnt].type = 1;
 72         }
 73     }
 74     for (int i = 1; i <= m - 1; ++i) {
 75         if (edge[i].w2 > x) continue;
 76         int u = edge[i].u, v = edge[i].v;
 77         if (dj_find(u) != dj_find(v)) {
 78             dj_merge(u, v);
 79             ans[++cnt].id = i, ans[cnt].type = 2;
 80         }
 81     }
 82 }
 83 
 84 int main() {
 85     n = get_num(), k = get_num(), m = get_num();
 86     for (int i = 1; i <= m - 1; ++i) {
 87         edge[i].u = get_num(), edge[i].v = get_num();
 88         edge[i].w1 = get_num(), edge[i].w2 = get_num();
 89         maxw = max(maxw, edge[i].w1);
 90     }
 91     int l = 1, r = maxw;
 92     while (l < r) {
 93         int mid = l + (r - l) / 2;
 94         if (check(mid)) r = mid;
 95         else l = mid + 1;
 96     }
 97     printf("%d
", l);
 98     build(l);
 99     sort(ans + 1, ans + n);
100     for (int i = 1; i <= n - 1; ++i)
101         printf("%d %d
", ans[i].id, ans[i].type);
102     return 0;
103 }

AC代码（洛谷、二分）