DDOSvoid's Blog

2020年广西省CCPC大学生程序设计竞赛 B Longest Road

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

简要题意：给定一个有 $n$ 个点 $m$ 条边的无向图，边有黑白两种颜色，要求一棵有 $k$ 条白边的生成树，且该树的最长边的权值最小

$n\le 10^5,m\le 2\times 10^5$

Solution

我们考虑二分答案

然后我们先加白边，这样可以求出最多有 $R$ 条白边

然后先加黑边，这样可以求出最少有 $L$ 条白边

如果 $L\le k\le R$，则一定有一颗只含有 $k$ 条白边的生成树

简单证明：我们考虑有 $R$ 条白边的生成树可以通过换边操作换成有 $L$ 条白边的生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define maxm 200010
#define ll long long
#define cE const Edge 
using namespace std;

int n, m, k;

struct Edge {
    int fr, to, w;
} e[maxm], E[maxm]; int c1, c2;

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; } 

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

bool check(int x) {
    int cnt = 0; init_fa(n); 
    for (int i = 1; i <= c1; ++i) {
        int u = e[i].fr, v = e[i].to, w = e[i].w; if (w > x) continue;
        int fu = find(u), fv = find(v); if (fu == fv) continue;
        fa[fu] = fv; ++cnt;
    } if (cnt < k) return 0;
    for (int i = 1; i <= c2; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].w; if (w > x) continue;
        int fu = find(u), fv = find(v); if (fu == fv) continue;
        fa[fu] = fv; ++cnt;
    } if (cnt < n - 1) return 0;

    init_fa(n); cnt = 0;
    for (int i = 1; i <= c2; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].w; if (w > x) continue;
        int fu = find(u), fv = find(v); if (fu == fv) continue;
        fa[fu] = fv; ++cnt;
    } if (cnt < n - k - 1) return 0;
    for (int i = 1; i <= c1; ++i) {
        int u = e[i].fr, v = e[i].to, w = e[i].w; if (w > x) continue;
        int fu = find(u), fv = find(v); if (fu == fv) continue;
        fa[fu] = fv; ++cnt;
    } return cnt == n - 1; 
    
}

void work() {
    cin >> n >> m >> k; init_fa(n); c1 = c2 = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, z, k; cin >> x >> y >> z >> k;
        if (k == 1) ++c1, e[c1].fr = x, e[c1].to = y, e[c1].w = z;
        else ++c2, E[c2].fr = x, E[c2].to = y, E[c2].w = z; 
    }
    int l = 1, r = 1e9, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } cout << ans << "\n";
}


ll ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}