1 条题解

  • 0
    @ 2025-3-30 11:21:04
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 10000;
    const int MAXM = 20000;
    struct Edge
    {
        int u, v, w;
    };
    Edge e[MAXM + 5];
    int n, m, s, t;
    bool cmp(Edge a, Edge b)
    {
        return a.w < b.w;
    }
    int fa[MAXN + 5];
    int cnt[MAXN + 5];
    int findFa(int x)
    {
        if (fa[x] == x)
            return x;
        return fa[x] = findFa(fa[x]);
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m >> s >> t;
        if (s == t)
        {
            cout << 0;
            return 0;
        }
        for (int i = 1; i <= m; i++)
            cin >> e[i].u >> e[i].v >> e[i].w;
        // 并查集初始化
        for (int i = 1; i <= n; i++)
        {
            fa[i] = i;
            cnt[i] = 1;
        }
        // kruskal 算法
        sort(e + 1, e + m + 1, cmp);
        int sum = 0;
        for (int i = 1; i <= m; i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            int w = e[i].w;
            int faU = findFa(u);
            int faV = findFa(v);
            if (faU != faV)
            {
                if (cnt[faU] < cnt[faV])
                {
                    fa[faU] = faV;
                    cnt[faV] += cnt[faU];
                }
                else
                {
                    fa[faV] = faU;
                    cnt[faU] += cnt[faV];
                }
                if (findFa(s) == findFa(t))
                {
                    cout << w << "\n";
                    return 0;
                }
            }
        }
        return 0;
    }
    
    

    信息

    ID
    2201
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    22
    已通过
    11
    上传者