「APIO 2008」免费道路

题目大意：给定一张 $n$ 个点 $m$ 条边的无向图，每条边为黑色或白色，求一棵生成树使得其中恰好有 $k$ 条白边，输出任意一种方案。$n \leq 2 \times 10^4, m \leq 10^5$

优先加黑边，可以得到哪些白边是必须加的，于是先把必须加的白边加上，然后随意找其他的白边填满 $k$ 条，再添黑边即可。

#include <cstdio>
#include <algorithm>

const int N = 20005, M = 100005;

struct Edge {
    int u, v, c;
    bool f;
} e[M];

int fa[N], n, m, k;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
bool cmp1(Edge a, Edge b) {
    return a.c > b.c;
}
bool cmp2(Edge a, Edge b) {
    return a.c < b.c;
}
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
int main() {
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; ++i)
        e[i].u = read(), e[i].v = read(), e[i].c = read();

    std::sort(e + 1, e + m + 1, cmp1);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx != fy) {
            fa[fx] = fy;
            if (e[i].c == 0) e[i].f = 1;
        }
    }

    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i)
        if (e[i].f) fa[find(e[i].u)] = find(e[i].v), ++cnt1, ++cnt2;

    std::sort(e + 1, e + m + 1, cmp2);
    for (int i = 1; i <= m; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx != fy) {
            if (e[i].c == 0) {
                if (cnt1 == k) continue;
                ++cnt1;
            }
            fa[fx] = fy, e[i].f = 1, ++cnt2;
        }
    }
    if (cnt1 != k || cnt2 != n - 1) puts("no solution");
    else {
        for (int i = 1; i <= m; ++i)
            if (e[i].f) printf("%d %d %d\n", e[i].u, e[i].v, e[i].c);
    }

    return 0;
}

时间复杂度 $O(m \log m)$