POJ 1287 Networking【kruskal模板题】

题意：给出n个点 m条边，求最小生成树的权

思路：最小生树的模板题，直接跑一遍kruskal即可

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string.h>

using namespace std;

const int maxn = 5005;

struct node

{

    int u;

    int v;

    int w;

    bool operator< (const node &a)

    {

        return w < a.w;

    }

} edges[maxn];

int f[maxn];

int find(int x)

{

    return f[x] = f[x] == x ? x : find(f[x]);

}

int kruskal(int n, int m)

{

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

        f[i] = i;

    int cnt = 0;

    int ans = 0;

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

    {

        int u = edges[i].u;

        int v = edges[i].v;

        int w = edges[i].w;

        int t1 = find(u);

        int t2 = find(v);

        if(t1 != t2)

        {

            ans += w;

            f[t1] = t2;

            cnt++;

        }

        if(cnt == n - 1)

            break;

    }

    if(cnt < n - 1)

        return -1;

    else

        return ans;

}

int main()

{

    int n;

    while(scanf("%d", &n), n)

    {

        int m;

        scanf("%d", &m);

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

        {

            scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);

        }

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

        int ans = kruskal(n, m);

        cout << ans << endl;

    }

}

巴特西

POJ 1287 Networking【kruskal模板题】

最新文章

热门文章