1 条题解

  • 1
    @ 2023-1-16 17:22:28
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 100;
    const int MAXM = 10000;
    int n, m; // n个点 m条边
    struct Edge
    {
        int u, v, w;
    };
    Edge e[MAXM + 5];
    int eCnt;
    bool cmp(Edge a, Edge b)
    {
        return a.w < b.w;
    }
    int fa[MAXN + 5];
    int findFa(int x)
    {
        if (x == fa[x])
            return x;
        return fa[x] = findFa(fa[x]);
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        eCnt = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                eCnt++;
                cin >> e[eCnt].w;
                e[eCnt].u = i;
                e[eCnt].v = j;
            }
        }
        m = eCnt;
        // 排序
        sort(e + 1, e + m + 1, cmp);
        // 并查集初始化
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        // kruskal/避开环
        int ans = 0;
        int cnt = 0;
        for (int i = 1; i <= m; i++)
        {
            // e[i].u <-> e[i].v : e[i].w
            // 如果会构成环,就不选,否则就选
            int faU = findFa(e[i].u);
            int faV = findFa(e[i].v);
            if (faU != faV)
            {
                fa[faU] = faV;
                ans += e[i].w;
                cnt++;
            }
        }
        if (cnt == n - 1)
            cout << ans << "\n";
        else
            cout << "orz\n";
        return 0;
    }
    
    
    • 1

    信息

    ID
    569
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    (无)
    递交数
    44
    已通过
    23
    上传者