POJ 1287 Networking

浏览数：21 / 时间：2015年06月09日

题目链接：

poj.org/problem?id=1287

题目大意：

你被分派到去设计一个区域的连接点，给出你每个点对之间的路线，你需要算出连接所有点路线的总长度。

题目输入：

一个数字n 代表有 n个顶点，一个数字 m 有m条边。

接下来m行是 m条边的信息，起点终点权值

题目输出：

输出最小生成树的值

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 22220

struct Edge
{
    int s, e, w;
    Edge(int s=0,int e=0,int w=0):s(s), e(e), w(w) {}
    bool friend operator < (Edge A, Edge B)
    {
        return A.w < B.w;
    }
}P[maxn];
int n, m;
int Par[maxn];

void Init();
int Kruskal();
int GetPar(int a);
void Meger(int a,int b);

int main()
{
    int s, e, w;

    while(cin >> n, n)
    {
        cin >> m;
        Init();
        for(int i=0; i<m; i++)
        {
            cin >> s >> e >>w;

            P[i] = Edge(s,e,w);
        }
        sort(P, P+m);

        int ans = Kruskal();

        cout << ans << endl;
    }
    return 0;
}


void Init()
{
    for(int i=0; i<=n; i++)
    {
        Par[i]=i;
    }
}
int Kruskal()
{
    int sum = 0;
    int Nnode = 1;
    for(int i=0; i<m; i++)
    {
        if( GetPar(P[i].s) != GetPar(P[i].e) )
        {
            sum += P[i].w;
            Meger(P[i].s,P[i].e);
            Nnode ++;
        }
        if(Nnode == n)
            return sum;
    }
    return 0;
}

int GetPar(int a)
{
    if(Par[a] != a)
        Par[a] = GetPar(Par[a]);
    return Par[a];
}

void Meger(int a,int b)
{
    Par[GetPar(a)] = Par[GetPar(b)];
}