【题意】：给出n个点，m条边，边分为两种，一种是A公司的，一种是B公司的。边上有权值，问用n-1条边把n个点连起来的最小费用是多少，其中A公司的边刚好有k条。题目保证有解。

【题解】：很明显看到是求一颗最小生成树，不过有一个限制就是刚刚好有k条边是A公司的。想了很久不会做，看别人代码的。二分出一个最大值delta使得A公司的边加上这个值后再求MST时A公司的边有大于等于k条，然后答案就是cost of MST - k * delta。思想其实是加上一个delta值去逼近答案，最后可以求出这样的MST，如果最后求出的MST的A公司的边多于k条，一定存在与A公司等效且等价的B公司边，替换过来即可。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 struct Edge {
26     int u, v, w, id;
27     Edge(){}
28     Edge(int _u, int _v, int _w, int _id) {
29         u = _u, v = _v, w = _w, id = _id;
30     }
31     bool operator<(const Edge &x) const {
32         if(w != x.w) return w < x.w;
33         else return id < x.id;
34     }
35 }et[2][100050], e;
36 int tot, tot1;
37 int n, m, k, cost;
38 int fa[50050];
39 
40 int find(int x) {
41     return (x == fa[x]) ? x : fa[x] = find(fa[x]);
42 }
43 
44 bool merge(int u, int v) {
45     u = find(fa[u]), v = find(fa[v]);
46     if(u != v) {
47         fa[u] = v;
48         return true;
49     } else return false;
50 }
51 
52 bool check(int w) {
53     cost = 0;
54     int cnt = 0;
55     for(int i = 0; i < n; i++) fa[i] = i;
56     int i = 0, j = 0;
57     while(i < tot || j < tot1) {
58         if(et[0][i].w + w <= et[1][j].w) {
59             e = et[0][i++];
60             e.w += w;
61         } else e = et[1][j++];
62         if(merge(e.u, e.v)) {
63             if(!e.id) cnt++;
64             cost += e.w;
65         }
66     }
67     return cnt >= k;
68 }
69 
70 int main() {
71     int Case = 1;
72     while(~scanf("%d%d%d", &n, &m, &k)) {
73         tot = tot1 = 0;
74         for(int i = 0; i < m; i++) {
75             int u, v, w, id;
76             scanf("%d%d%d%d", &u, &v, &w, &id);
77             if(id) et[1][tot1++] = Edge(u, v, w, id);
78             else et[0][tot++] = Edge(u, v, w, id);
79         }
80         sort(et[0], et[0] + tot);
81         sort(et[1], et[1] + tot1);
82         et[0][tot].w = et[1][tot1].w = 1 << 30;
83         int l = -100, r = 100;
84         int w;
85         while(l <= r) {
86             int mid = (l + r) / 2;
87             if(check(mid)) w = mid, l = mid + 1;
88             else r = mid - 1;
89         }
90         check(w);
91         printf("Case %d: %d\n", Case++, cost - w * k); 
92     }
93     return 0;
94 }
95