Daleks' Invasion (easy)

发表于 分类于 ，

    给出一个n个节点m条边的无向有权图。

    我们修改第一条边的权值，让它的权值尽可能大并且第一条边仍然在最小生成树中。如果可以无限大，那么就修改为1e9

Daleks’ Invasion (easy)

Created by LXC on Sat Aug 5 15:09:55 2023

https://codeforces.com/problemset/problem/1184/E1

ranting: 1900

tag: graphs, trees

problem

给出一个n个节点m条边的无向有权图。

我们修改第一条边的权值，让它的权值尽可能大并且第一条边仍然在最小生成树中。如果可以无限大，那么就修改为1e9

solution

可以二分答案，然后求最小生成树验证。这里没有用这种方法。

我们直接用kuskal算法对除去第一条边的图求最小生成树。

由于我们对边权由小到大的排序好了。当遍历到一条边其两端不在一个连通块则加入最小生成树，此时我们额外判断这两端与第一条边的两端是否分别在同一个连通块，如果是则第一条边的边权最大可以修改为当前边的边权。

code

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 100005
#define MOD 998244353
using namespace std;

int st[N];

int ufind(int x) {
    return st[x] < 0 ? x : st[x] = ufind(st[x]);
}

struct Node {
    int u, v, w;
    bool operator<(const Node& o) const { return w < o.w; }
};

void sol() {
    memset(st, -1, sizeof(st));
    int n, m;
    cin >> n >> m;
    vector<Node> a(m);
    for (auto& i : a) {
        cin >> i.u >> i.v >> i.w;
    }
    sort(a.begin() + 1, a.end());
    for (int i = 1; i < m; i++) {
        int x = ufind(a[i].u), y = ufind(a[i].v);
        if (x != y) {
            int p = ufind(a[0].u), q = ufind(a[0].v);
            if (x == p && y == q || x == q && y == p) {
                cout << a[i].w << "\n";
                return;
            }
            st[x] = y;
        }
    }
    cout << "1000000000\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}