1 条题解

  • 1
    @ 2023-9-30 13:22:38

    这么简单的题怎么能没题解呢

    #include <cstdio>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    int n, m, f[40001], vis[40001], x, y, z;
    struct data
    {
        int a, b, c;
    } e[100001];
    int comp(data a, data b)
    {
        return a.c > b.c;
    }
    int find(int x)
    {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            cin >> e[i].a >> e[i].b >> e[i].c;
        for (int i = 1; i <= n; i++)
            f[i] = i;
        sort(e + 1, e + m + 1, comp);
        for (int i = 1; i <= m; i++)
        {
            x = find(e[i].a);
            y = find(e[i].b);
            if (x == y)
            {
                cout << e[i].c;
                return 0;
            }
            else
            {
                if (vis[e[i].a])
                {
                    z = find(vis[e[i].a]);
                    f[y] = z;
                }
                else
                    vis[e[i].a] = e[i].b;
     
                if (vis[e[i].b])
                {
                    z = find(vis[e[i].b]);
                    f[x] = z;
                }
                else
                    vis[e[i].b] = e[i].a;
            }
        }
        cout << 0;
        return 0;
    }
    
    • 1