题解 | #钢筋切割#

B交通改造：Kruskal 思路：1.接受改造的道路能够令所有的交叉路口直接或间接相连2.并且改造的道路数量应尽可能的少.这两条信息提示我们最终形成的是一颗生成树。但并非是最小生成树，而是最大边权最小生成树。那么只需要二分答案，每次看是否能够形成一棵生成树即可。形成的生成树的充要条件为共有n-1条边

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
    int a, b, w;

    bool operator< (const Edge& W)const
    {
        return w < W.w;
    }
}edges[M];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kruskal(int x)
{
    for (int i = 1; i <= n; i++) p[i] = i;    // 初始化并查集
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b && w <= x)
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }
    if (cnt < n - 1) return 0;
    return 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = { a, b, w };
    }
    sort(edges, edges + m);
    int l = 0, r = 10000;
    while (l < r)
    {    
        int mid = (l + r ) / 2;
        if (kruskal(mid) ==0)
        {
            l = mid + 1;
        }
        else r = mid;
    }
    cout << n - 1 << " ";
    cout << l << endl;
    return 0;
}