Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2901 Solved: 1196
[Submit][Status][Discuss]
Description
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
Input
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
Output
一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。
Sample Input
2 2 1 0 1 1 1 0 1 2 0
Sample Output
2
HINT
原数据出错，现已更新 by liutian,但未重测---2016.6.24
Source
对于图上的最小生成树
如果我们得到的最小生成树上的白边小于$need$条，那么说明白边的权值整体偏大，
那么我们考虑对所有的白边减去一个权值，这样最小生成树上的白边就会变多
这个过程很显然具有单调性，于是可以二分减去的权值
注意一个坑：当权值相同的时候优先选择白边
代码语言：javascript复制#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1e6 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, M, need;
struct Edge {
int u, v, w, opt;
bool operator <(const Edge &rhs) const {
return w == rhs.w ? opt < rhs.opt : w < rhs.w;
}
}E[MAXN], e[MAXN];
int Val = 0, fa[MAXN];
int siz[MAXN];
int find(int x) {
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
int unionn(int x, int y) {
int fx = find(x), fy = find(y);
if(siz[fx] < siz[fy]) swap(fx, fy);
fa[fy] = fx;
}
bool check(int x) {
Val = 0;
for(int i = 1; i <= M; i ) {
E[i] = e[i];
if(e[i].opt == 0) E[i].w = x;
}
for(int i = 1; i <= N; i )
fa[i] = i, siz[i] = 1;
int tot = 0, white = 0;
sort(E 1, E M 1);
for(int i = 1; i <= M; i ) {
if(find(E[i].u) != find(E[i].v)) {
unionn(E[i].u, E[i].v);
Val = E[i].w; tot ;
if(E[i].opt == 0) white ;
}
if(tot == N - 1) break;
}
return white >= need;
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read(), M = read(), need = read();
for(int i = 1; i <= M; i ) {
int x = read() 1, y = read() 1, z = read(), opt = read();
e[i] = (Edge){x, y, z, opt};
}
int l = -110, r = 110, ans = 0;
while(l <= r) {
int mid = l r >> 1;
if(check(mid)) ans = Val - mid * need, l = mid 1;
else r = mid - 1;
}
printf("%d", ans);
}
