POJ 1287：Networking（最小生成树Kruskal）

Description

Input

Output

Sample Input

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

Sample Output

0
17
16
26

题意：

P个点，R对边，找出最小通路和

分析：

长度为边权的最小生成树问题

kruskal & 并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn=5100;

int r[maxn];
int n, m;

struct node
{
    int x;
    int y;
    int cost;
};
node a[maxn];

bool cmp ( node a, node b )
{
    return a.cost<b.cost;
}

void init()
{
    for( int i=0; i<n; i++ )
        scanf( "%d%d%d", &a[i].x, &a[i].y, &a[i].cost );
    sort( a, a+n, cmp );
    for( int i=0; i<n; i++ )
        r[i] = i;
}

int find( int x )
{
    return r[x]==x? x : r[x] = find( r[x] );
}

void kruskal()
{
    int cnt = 0;
    int ans = 0;
    int x; int y;
    for( int i=0; i<n; i++ )
    {
        x = find( a[i].x );
        y = find( a[i].y );
        if( x!=y )
        {
            cnt++;
            ans += a[i].cost;
            if( cnt == m-1 )
                break;
            r[y] = x;
        }
    }
    printf( "%d\n", ans );
}

int main()
{
    while( scanf( "%d", &m )==1 &&m )
    {
        scanf( "%d", &n );
        init();
        kruskal();
    }
    return 0;
}