首页 > 代码库 > bzoj 2654 tree - 二分法 - 最小生成树
bzoj 2654 tree - 二分法 - 最小生成树
<style></style>
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
Input
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
Output
一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。
Sample Input
2 2 10 1 1 10 1 2 0
Sample Output
2
Hint
原数据出错，现已更新 by liutian,但未重测---2016.6.24
显然是MST，但是在Kruskal的过程中我们无法控制白边的数量。如果考虑修改边值，可以发现如果给白边的边权都加上一个delta，那么白边的数量随着delta的增大而减小。所以可以二分它去控制白边的数量。
Code
1 /** 2 * bzoj 3 * Problem#2654 4 * Accepted 5 * Time:1892ms 6 * Memory:3052k 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<ctime> 11 #include<cctype> 12 #include<cstring> 13 #include<cstdlib> 14 #include<fstream> 15 #include<sstream> 16 #include<algorithm> 17 #include<map> 18 #include<set> 19 #include<stack> 20 #include<queue> 21 #include<vector> 22 #include<stack> 23 #ifndef WIN32 24 #define Auto "%lld" 25 #else 26 #define Auto "%I64d" 27 #endif 28 using namespace std; 29 typedef bool boolean; 30 const signed int inf = (signed)((1u << 31) - 1); 31 #define smin(a, b) a = min(a, b) 32 #define smax(a, b) a = max(a, b) 33 #define max3(a, b, c) max(a, max(b, c)) 34 #define min3(a, b, c) min(a, min(b, c)) 35 template<typename T> 36 inline boolean readInteger(T& u){ 37 char x; 38 int aFlag = 1; 39 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 40 if(x == -1) { 41 ungetc(x, stdin); 42 return false; 43 } 44 if(x == ‘-‘){ 45 x = getchar(); 46 aFlag = -1; 47 } 48 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 49 ungetc(x, stdin); 50 u *= aFlag; 51 return true; 52 } 53 54 typedef class union_found{ 55 public: 56 int *f; 57 union_found():f(NULL) {} 58 union_found(int points) { 59 f = new int[(const int)(points + 1)]; 60 clear(points); 61 } 62 int find(int x) { 63 if(f[x] != x) return f[x] = find(f[x]); 64 return f[x]; 65 } 66 void unit(int fa, int so) { 67 int ffa = find(fa); 68 int fso = find(so); 69 f[fso] = ffa; 70 } 71 boolean connected(int a, int b) { 72 return find(a) == find(b); 73 } 74 void clear(int points) { 75 for(int i = 0; i <= points; i++) 76 f[i] = i; 77 } 78 }union_found; 79 80 int delta = 0; 81 82 typedef class Edge { 83 public: 84 int from; 85 int end; 86 int val; 87 boolean col; 88 89 inline int getVal() const { 90 if(col) return val + delta; 91 return val; 92 } 93 }Edge; 94 95 boolean operator < (const Edge& a, const Edge& b) { 96 return a.getVal() < b.getVal(); 97 } 98 99 int n, m, lim;100 union_found uf;101 Edge* edge;102 103 inline void init() {104 readInteger(n);105 readInteger(m);106 readInteger(lim);107 uf = union_found(n);108 edge = new Edge[(const int)(m + 1)];109 for(int i = 0; i < m; i++) {110 readInteger(edge[i].from);111 readInteger(edge[i].end);112 readInteger(edge[i].val);113 readInteger(edge[i].col);114 edge[i].col ^= 1;115 }116 }117 118 int res = 0;119 int kruskal(int mid) {120 delta = mid;121 res = 0;122 uf.clear(n);123 sort(edge, edge + m);124 int fw = 0, fin = 0;125 for(int i = 0; i < m; i++) {126 if(!uf.connected(edge[i].from, edge[i].end)) {127 uf.unit(edge[i].from, edge[i].end);128 fw += edge[i].col, fin ++, res += edge[i].val;129 }130 }131 return fw;132 }133 134 135 inline void solve() {136 int l = -100, r = 100, c;137 while(l <= r) {138 int mid = (l + r) >> 1;139 if((c = kruskal(mid)) < lim) r = mid - 1;140 else if(c > lim) l = mid + 1;141 else break;142 }143 printf("%d\n", res);144 }145 146 int main() {147 init();148 solve();149 return 0;150 }
bzoj 2654 tree - 二分法 - 最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。