数据结构实验之图论九：最小生成树

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

Output

每组输出占一行，仅输出最小花费。

Example Input

Example Output

2
0

Hint

Author

//最小生成树（贪心算法，Prim算法（让小树长大））
//1.树：无回路，V个定点一定有V-1条边
//2.生成：包含图的全部顶点，V-1条边都在图里（向生成树中任加一条边都一定构成回路）
//3.最小：边的权重和最小
//最小生成树存在的充分必要条件是图是连通的
//题目与村村通公路相同，但不考虑不连通输出-1 的情况并且有一点注意（以下注释中的：如果权值小于INF才将权值记录）
#include <iostream>
#include <memory.h>

using namespace std;

#define INF 0x3f3f3f3f

int n,m,sum;
int po[1024][1024];
int vi[1024];
int lowcost[1024];

void Prime()
{
int i;
vi[1]=1;
for(i=2;i<=n;i++)
{
lowcost[i]=po[1][i];
}
for(i=2;i<=n;i++)
{
int temp=INF,j,k;
for(j=1;j<=n;j++)
{
if(!vi[j] && lowcost[j]<temp)
{
temp=lowcost[j];
k=j;
}
}
vi[k]=1;
sum+=temp;
for(j=1;j<=n;j++)
{
if(!vi[j] && lowcost[j]>po[k][j])
{
lowcost[j]=po[k][j];
}
}
}
cout<<sum<<endl;
}

int main()
{
while(cin>>n>>m)
{
memset(po,INF,sizeof(po));
memset(vi,0,sizeof(vi));
sum=0;
int i;
for(i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(c<po[a][b])//注意：如果权值小于INF才将权值记录
{
po[a][b]=po[b][a]=c;
}
}
Prime();
}
return 0;
}

秒客网

数据结构实验之图论九：最小生成树