数据结构实验之图论九：最小生成树
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。
Input
输入包含多组数据，格式如下。
第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)
剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。
Output
每组输出占一行，仅输出最小花费。
Sample Input
3 2
1 2 1
1 3 1
1 0
Sample Output
2
0
题解：prim算法来求最小生成树，同SDUT-3362_村村通公路。
不过这道题更简单点，不用判定是否连通，题目貌似都是连通的数据。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int s[1050][1050];/*利用邻接矩阵来记录图*/
int n;/*n节点数量*/
int f[1050];/*记录点是否被遍历过*/
int INF = 1e9+7;/*相当于无穷大*/
int prim()
{
int i,sum,j,MIN,k;
int dis[1050];
for(i=1;i<=n;i++)
{
f[i] = 0;
dis[i] = s[1][i];
}
f[1] = 1;
sum = 0;
for(i=1;i<n;i++)
{
MIN = INF;
k = -1;
for(j=1;j<=n;j++)
{
if(!f[j]&&dis[j]<MIN)
{
MIN = dis[j];
k = j;
}
}
f[k] = 1;
sum += MIN;
for(j=1;j<=n;j++)
{
if(!f[j]&&dis[j]>s[k][j])
dis[j] = s[k][j];
}
}
return sum;
}
int main()
{
int m,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s[i][j] = i==j?0:INF;
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c<s[a][b])
s[a][b] = s[b][a] = c;
}
printf("%d
",prim());
}
return 0;
}