题解 P2619 【[国家集训队2]Tree I】

· · 题解

年轻人的第一道国家集训队题目

如果我们不做任何处理，直接跑MST（Minimum Spanning Tree，最小生成树），结果会有三种：

第一种情况自然是最好的

剩下两种情况如何解决？

引起白边少的原因：黑边的边权相对较小，程序贪心地选择了更多的黑边

引起白边多的原因：白边的边权相对较小，程序贪心地选择了更多的白边

那么如果我们给白边相应地减去/加上一些边权，不就可以达成目标了？

考虑二分答案。

我们二分一个 add 表示我们当前要给白边加上 add 来达成目标

边界分别是边权最小值（-100）和边权最大值（100）

由于题面保证有答案，所以直接输出 ans - add \times \text{Need} 即可，其中 ans 为（加上边权后）最小生成树的权值和

Check(mid) 怎么写？

我们将所有白边的边权加上add（即mid），跑一遍最小生成树，判断一下拿到的白色边数量是否大于等于要求的数量，如果是就更新一下左边界并记当前的mid为tans，否则就更新一下右边界

注意不要忘了把边权减回来

（不要在意 tans 是什么意思）

刚才我们不是记录了一下tans吗，这个tans就相当于是一个正确的、能选出正好 \text{Need} 条白边的 add 值，再将所有白边的边权都加上这个 tans，跑一遍最小生成树即可

答案不要忘了减去加上的边权（也就是 \text{Need} \times tans ）

那么最后的答案就是 \text{Kruskal()} - \text{Need} \times tans

代码实现

#include <algorithm>
#include <iostream>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

#define WHITE 0
#define BLACK 1

using std::cin;
using std::cout;
using std::endl;
using std::max;

const int MAXV = 50000 + 10;
const int MAXE = 100000 + 10;
const int MAXW = 100;

struct Edge {
    int prev, next, weight, add;
    bool color;
    // 1 -> black, 0 -> white

    Edge() { prev = next = weight = color = add = 0; }

    bool operator < (const Edge &that) const {
        if (weight == that.weight) return color < that.color;
        return weight < that.weight;
    }
} edge[MAXE << 1];

int V, E, Need, cnt, ans;

int U[MAXV << 1];

int Find(int x) {
    if (U[x] == x) return U[x];
    return U[x] = Find(U[x]);
}

bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    U[x] = y;
    return true;
}

int Kruskal() {
    int whiteEdge = 0;
    for (int i = 1; i <= V; ++i) U[i] = i;
    std::sort(edge + 1, edge + 1 + E);
    int tot = 0;
    ans = 0;
    for (int i = 1; i <= E; ++i) {
        if (Union(edge[i].prev, edge[i].next)) 
            ans += edge[i].weight, ++tot, whiteEdge += (edge[i].color == WHITE);
        if (tot == V - 1) break;
    }
    return whiteEdge;
}

bool Check(int add) {
    for (int i = 1; i <= E; ++i) {
        if (edge[i].color == WHITE) edge[i].weight += add;
    }
    bool Ans = (Kruskal() >= Need);
    for (int i = 1; i <= E; ++i) {
        if (edge[i].color == WHITE) edge[i].weight -= add;
    }
    return Ans;
}

int main() {
    IMPROVE_IO();
    cin >> V >> E >> Need;
    for (int i = 1; i <= E; ++i) {
        cin >> edge[i].prev >> edge[i].next >> edge[i].weight >> edge[i].color;
        ++edge[i].prev;
        ++edge[i].next;
    }
    int l = -MAXW, r = MAXW;
    int Run = 0;
    while (l <= r) {
        int mid = ((l + r) >> 1);
        if (Check(mid)) {
            l = mid + 1;
            Run = mid;
        } else {
            r = mid - 1;
        }
    }
    Check(Run);
    cout << ans - Need * Run << endl;
    return 0;
}