[bzoj2654] tree 最小生成树kruskal+二分

题目描述

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。

输入格式

第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

输出格式

一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

样例

样例输入

样例输出

数据范围与提示

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

题解：

我们要求一个最小生成树，树中必须恰好包含need条边

在常用的kruskal算法中，一旦边权确定，黑白边就是等价的，但我们要找恰好need条边，所以要让白边尽可能的“特殊”。

想让白边“特殊”，只能给白边改权值。

设用当前的权值求出的最小生成树所含有的白边>need，我们要减少白边数量，就要给每个白边加权值；小于need，要增加白边数量，给白边减权值（加上一个负权）。

那真正的权值怎么求？

我们在kruskal中记录白边个数，白边个数>=need时更新权值：ans=ans-mid×need

一定是白边个数>=need时更新权值，博主在这里卡了半天。

具体原因博主也是看的大佬的题解，现给出解释：

如果在你的二分过程中如果给白边加上mid,你得到的白边数比need大。

给白边加上mid+1,你得到的白边比need小。

这种情况看似没法处理。

但是考虑一下kruskal的加边顺序

可以发现如果出现这种情况，一定是有很多相等的白边和黑边。

因为你排序的时候如果有两条相同权值的黑边和白边，肯定是要把白边排在前面

因为数据保证合法，所以我们可以把一些白边替换成黑边。

所以我们要在白边数>=need的时候更新答案。

那么这个增加的权值如何确定？

二分答案

二分枚举要加上的权值，然后给每个白边加上权值，跑kruskal，出的最小生成树所含有的白边>need，l=mid+1，小于need，r=mid-1。

跑完每遍kruskal后把白边的权值再减回去。

二分结束后，输出当前的实际权值。

#include <cstdio>

#include <iostream>

#include <algorithm>

#define MAXE 100005

#define MAXV 50005

using namespace std;

int v, e, need;

struct node {

    int fr, to, w, col;

    friend bool operator < (const node &a, const node &b) {

        return (a.w == b.w) ? (a.col < b.col) : (a.w < b.w);

    }

} edge[MAXE];

int l = -101, r = 101, mid, ans = 0, res = 0;

int fa[MAXV];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int kruskal(int mid) {

    int sum_edge = 0, sum_white = 0;

    res = 0;

    for (int i = 1; i <= v; i++) fa[i] = i;

    for (int i = 1; i <= e; i++) {

        if (!edge[i].col)

            edge[i].w += mid;

    }

    sort(edge + 1, edge + e + 1);

    for (int i = 1; i <= e; i++) {

        int x = find(edge[i].fr), y = find(edge[i].to);

        if (x != y) {

            fa[x] = y;

            res += edge[i].w;

            sum_edge++;

            if (!edge[i].col)

                sum_white++;

        }

        if (sum_edge == v - 1)

            break;

    }

    for (int i = 1; i <= e; i++) {

        if (!edge[i].col)

            edge[i].w -= mid;

    }

    return sum_white;

}

int main() {

    scanf("%d%d%d", &v, &e, &need);

    for (int i = 1; i <= e; i++) {

        scanf("%d%d%d%d", &edge[i].fr, &edge[i].to, &edge[i].w, &edge[i].col);

        edge[i].fr++, edge[i].to++;

    }

    while (l <= r) {

        mid = (l + r) >> 1;

        if (kruskal(mid) >= need) {

            l = mid + 1;

            ans = res - mid * need;

        } else

            r = mid - 1;

    }

    printf("%d\n", ans);

    return 0;

}

巴特西