P2619 [国家集训队]Tree I

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

克鲁斯卡尔算法 求最小生成树的时候，将所有的边按照边权排序。现在对白色边的个数有限制，可以将所有的白色边的权值都增加一个数，使得一些白色边被黑色边替代了，二分这个增加的数，这就是 wqs二分 的一种应用。

考虑一种情况，当前的白色边增加 $mid$ 后，白色边的个数 $cnt < need$ ，而 $mid + 1$ 使得 $cnt > need$ ，出现这种情况一定是有白色边和黑色边的边权一样，现在我们优先取白色边，当 $cnt$ 取到大于 $need$ 的第一个数时，将多余的白色边替换为黑色边，即为答案。

另外，每次都对所有边排序太慢了，而白色边的边权时同时增加的，黑白两色的顺序各自不变，所以将黑白两色的边分类存储，分别排序。使用时归并即可。

查看代码

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5e4 + 10, M = 1e5 + 10;
int n, m, s, p[N];
struct Edge
{
    int u, v, w;
    bool operator<(const Edge &_) const
    {
        return w < _.w;
    }
};
vector<Edge> e[2];
int fa(int x)
{
    return x == p[x] ? x : p[x] = fa(p[x]);
}
bool add(Edge x)
{
    if (fa(x.u) == fa(x.v))
        return false;
    p[p[x.u]] = p[x.v];
    return true;
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int u, v, w, c; m; m--)
    {
        scanf("%d%d%d%d", &u, &v, &w, &c);
        e[c].push_back((Edge){u, v, w});
    }
    sort(e[0].begin(), e[0].end());
    sort(e[1].begin(), e[1].end());
    int l = -100, r = 100;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        for (int i = 0; i < n; i++)
            p[i] = i;
        int x = 0, y = 0, ans = 0;
        while (x < e[0].size() && y < e[1].size())
            e[0][x].w + mid <= e[1][y].w ? ans += add(e[0][x++]) : add(e[1][y++]);
        while (x < e[0].size())
            ans += add(e[0][x++]);
        ans < s ? r = mid - 1 : l = mid;
    }
    for (int i = 0; i < n; i++)
        p[i] = i;
    int x = 0, y = 0, ans = 0;
    while (x < e[0].size() && y < e[1].size())
        if (e[0][x].w + l <= e[1][y].w)
            ans += (e[0][x].w + l) * add(e[0][x]), x++;
        else
            ans += e[1][y].w * add(e[1][y]), y++;
    while (x < e[0].size())
        ans += (e[0][x].w + l) * add(e[0][x]), x++;
    while (y < e[1].size())
        ans += e[1][y].w * add(e[1][y]), y++;
    printf("%d\n", ans - s * l);
    return 0;
}