BZOJ 2654: tree(二分 最小生成树)

2018-06-17 20:35:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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$条,那么说明白边的权值整体偏大,

那么我们考虑对所有的白边减去一个权值,这样最小生成树上的白边就会变多

这个过程很显然具有单调性,于是可以二分减去的权值

注意一个坑:当权值相同的时候优先选择白边

 

#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);
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:EffectiveC++笔记 第3章

下一篇:Opencv3.4:显示一张图片