E3-G Swamp

题目描述

Oh no! Q 被派到了一片沼泽做生态调查，他需要前往沼泽的 $n 个地点（编号为个地点（编号为 1,2,…,n$ ），Q一开始在 1 号点。这 n 个地点中有 m 条边使它们联通。连接$ u,v $的边会经过深度为 hu,vh_{u,v} 的泥潭。有洁癖的 Q 想让他的鞋子尽可能干净，请你帮他算出从 1 号点开始走完剩下的 $(n−1) $个地点，Q 需要经过的最深泥潭的最小深度。

输入

第一个数为数据组数 t(5≤t≤15).t (5≤t≤15).

对于每组数据，每行2个整数n,m(1≤n≤2×105,1≤m≤4×105).n,m (1≤n≤2×10^5,1≤m≤4×10^5).

接下来m行，每行三个整数u,v,hu,v(1≤u,v≤n),hu,vu,v,h_{u,v} (1≤u,v≤n), h_{u,v} 在 int 范围内，代表地点 u 到地点 v 有一条通路，且需要经过深度为$ h_{u,v}$ 的泥潭。

输出

对于每组数据，输出一行，Q从 1 号点开始走完剩下的$ (n−1) $个地点， 需要经过的最深泥潭的最小深度。

输入样例

1
2
3
4
5
1
3 3
1 2 1
1 3 2
2 3 3

输出样例

1
2

题目分析

此题要求1号顶点到所有顶点经过的边中权值最大的边的最小值。这里本质上是寻找一个边，因此我们可以通过二分法寻找。

首先将所有边按照深度从小到大排序，然后开始二分查找。查找左边界为0，右边界为最长边，建立一个并查集，将所有深度小于midmid所指边的边所连两点加入集合。之后检测所有节点是否有公共祖先1号节点，即检测所选边包含的所有顶点是否连通。如果连通则更新答案为midmid所指边的深度，如果不连通则说明midmid所指边的深度太小了，符合条件的边不足，需要left=mid+1left = mid+1之后继续查找。

示例代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge
{
    int u, v;
    long long h;

    bool operator<(const Edge &other) const
    {
        return h < other.h;
    }
};

class UnionFind
{
public:
    UnionFind(int n)
    {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
            parent[i] = i;
        }
    }

    int find(int u)
    {
        if (parent[u] != u)
        {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void unionSets(int u, int v)
    {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV)
        {
            if (rank[rootU] > rank[rootV])
            {
                parent[rootV] = rootU;
            }
            else if (rank[rootU] < rank[rootV])
            {
                parent[rootU] = rootV;
            }
            else
            {
                parent[rootV] = rootU;
                ++rank[rootU];
            }
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
};

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;

        vector<Edge> edges(m);
        for (int i = 0; i < m; ++i)
        {
            cin >> edges[i].u >> edges[i].v >> edges[i].h;
        }
        sort(edges.begin(), edges.end());

        long long left = 0, right = m - 1, answer = edges[right].h;

        while (left <= right)
        {
            long long mid = left + (right - left) / 2;

            UnionFind uf(n);
            for (const auto &edge : edges)
            {
                if (edge.h <= edges[mid].h)
                {
                    uf.unionSets(edge.u, edge.v);
                }
            }

            bool connected = true;
            for (int i = 2; i <= n; ++i)
            {
                if (uf.find(1) != uf.find(i))
                {
                    connected = false;
                    break;
                }
            }

            if (connected)
            {
                answer = edges[mid].h;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }

        cout << answer << endl;
    }
    return 0;
}