CCF-CSP题解 201812-4 数据中心

题目要求最长边最小的生成树。好吧，这就是一道kruskal MST题。

#include <bits/stdc++.h>

const int maxn = 50000;

const int maxm = 100000;

using namespace std;

struct tEdge

{

    int u, v;

    int t;

    bool operator < (const tEdge &y) const

    {

        return t < y.t;

    }

};

tEdge edge[maxm+10];

int cnt = 1;

int fa[maxn+10];

int getFa(int x)

{

    if (x == fa[x])

        return x;

    return fa[x] = getFa(fa[x]);

}

int main()

{

    int n, m, root;

    scanf("%d%d%d", &n, &m, &root);

    for (int i = 1, u, v, t; i <= m; i++)

    {

        scanf("%d%d%d", &u, &v, &t);

        edge[cnt].u = u;

        edge[cnt].v = v;

        edge[cnt++].t = t;

    }

    sort(edge + 1, edge + 1 + m);

    for (int i = 1; i <= n; i++)

        fa[i] = i;

    int ans = -1;

    for (int i = 1, temp = 0; temp != n - 1; i++)

    {

        int rx = getFa(edge[i].u), ry = getFa(edge[i].v);

        if (rx != ry)

        {

            fa[rx] = ry;

            temp ++;

            ans = edge[i].t;

        }

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

CCF-CSP题解 201812-4 数据中心

最新文章

热门文章