经典的k条白边MST
带权二分，按照套路我们要选择尽量少的白边。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int N = 100010; 5 6 int D; 7 8 struct Edge { 9 int x, y, val, col; 10 inline bool operator <(const Edge &w) const { 11 if(val - D * col == w.val - D * w.col) { 12 return col < w.col; 13 } 14 return val - D * col < w.val - D * w.col; 15 } 16 }edge[N]; 17 18 int n, m, k, ans; 19 20 namespace ufs{ 21 int fa[N]; 22 int find(int x) { 23 if(x == fa[x]) { 24 return x; 25 } 26 return fa[x] = find(fa[x]); 27 } 28 inline void merge(int x, int y) { 29 fa[find(x)] = find(y); 30 return; 31 } 32 inline bool check(int x, int y) { 33 return find(x) == find(y); 34 } 35 inline void clear() { 36 for(int i = 1; i <= n; i++) { 37 fa[i] = i; 38 } 39 return; 40 } 41 } 42 43 inline int check(int mid) { 44 ufs::clear(); 45 D = mid; 46 ans = 0; 47 int cnt = 0; 48 std::sort(edge + 1, edge + m + 1); 49 for(int i = 1; i <= m; i++) { 50 if(!ufs::check(edge[i].x, edge[i].y)) { 51 cnt += edge[i].col; 52 ans += edge[i].val - D * edge[i].col; 53 ufs::merge(edge[i].x, edge[i].y); 54 } 55 } 56 return cnt; 57 } 58 59 int main() { 60 scanf("%d%d%d", &n, &m, &k); 61 for(int i = 1; i <= m; i++) { 62 scanf("%d%d%d%d", &edge[i].x, &edge[i].y, &edge[i].val, &edge[i].col); 63 edge[i].x++; 64 edge[i].y++; 65 edge[i].col ^= 1; 66 } 67 68 int l = -150, r = 150; 69 while(l < r) { 70 int mid = (l + r + 1) >> 1; 71 int t = check(mid); 72 //printf("[%d %d] mid = %d cnt = %d ", l, r, mid, t); 73 if(t == k) { 74 printf("%d ", ans + k * mid); 75 return 0; 76 } 77 if(t < k) { 78 l = mid; 79 } 80 else { 81 r = mid - 1; 82 } 83 } 84 check(r); 85 printf("%d ", ans + k * r); 86 return 0; 87 }