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

2023-07-28 18:07:46

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

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

Source

对于图上的最小生成树

如果我们得到的最小生成树上的白边小于$need$条，那么说明白边的权值整体偏大，

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

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

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

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN = 1e6 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 = , 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 = ;

    for(int i = ; i <= M; i++) {

        E[i] = e[i];

        if(e[i].opt == ) E[i].w += x;

    }

    for(int i = ; i <= N; i++)

        fa[i] = i, siz[i] = ;

    int tot = , white = ;

    sort(E + , E + M + );

    for(int i = ; 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 == ) white++;

        }

        if(tot == N - ) break;

    }

    return white >= need;

}

main() {

    #ifdef WIN32

    freopen("a.in", "r", stdin);

    #endif

    N = read(), M = read(), need = read();

    for(int i = ; i <= M; i++) {

        int x = read() + , y = read() + , z = read(), opt = read();

        e[i] = (Edge){x, y, z, opt};

    }

    int l = -, r = , ans = ;

    while(l <= r) {

        int mid = l + r >> ;

        if(check(mid)) ans = Val - mid * need, l = mid + ;

        else r = mid - ;

    }

    printf("%d", ans);

}

码农公寓