如何求解poj1287中的最小生成树问题？

本文共计522个文字，预计阅读时间需要3分钟。

题目链接：[POJ 1287](http://poj.org/problem?id=1287)

题意：给定n个点，m条边，每条边需要花费一定的代价才能联通，求n个点联通的最小花费。

解析：最小生成树问题。可以使用普里姆算法或克鲁斯卡尔算法求解。以下是普里姆算法的步骤：

1. 选择一个点作为起点，初始化最小生成树的边集合为空。

2.将起点加入最小生成树。

3.遍历所有点，对于不在最小生成树中的点，计算其到最小生成树中所有点的最小边。

4.选择最小边，将对应的点加入最小生成树，并将这条边加入边集合。

5.重复步骤3和4，直到所有点都加入最小生成树。

使用普里姆算法可以找到n个点联通的最小花费。

题目链接：​​poj.org/problem?id=1287​​​
题意：类似n个点，m条边，每条边需要花费一定的代价才能联通，问你把n个点联通的最小花费
解析：最小生成树裸题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1e5+100;
struct node
{
int x,y,v;
bool operator < (const node &b)const
{
return v<b.v;
}
}a[maxn];
int fa[maxn];
void init(int n)
{
for(int i=0;i<=n;i++)
fa[i] = i;
}
int getfa(int x)
{
if(x==fa[x])
return x;
return fa[x] = getfa(fa[x]);
}
int main(void)
{
int n,m;
while(~scanf("%d",&n)&&n)
{
scanf("%d",&m);
init(n);
for(int i=0;i<m;i++)
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v);
sort(a,a+m);
int ans = 0;
for(int i=0;i<m;i++)
{
int t1 = getfa(a[i].x);
int t2 = getfa(a[i].y);
if(t1!=t2)
{
fa[t1] = t2;
ans += a[i].v;
}
}
printf("%d\n",ans);
}
return 0;
}