图结构练习——最小生成树
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。
输入
输入包含多组数据，格式如下。
第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n<=100)
剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。
输出
每组输出占一行，仅输出最小花费。
示例输入
3 2
1 2 1
1 3 1
1 0
示例输出
2
0
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct vode
{
int u,v,w;
}edge[];
int m,n;
int f[];
int cmp(const void *a,const void *b)//注意此函数的使用方法和定义方法
{
struct vode *c=(struct vode *)a;
struct vode *d=(struct vode *)b;
return c->w-d->w;
}
int find(int v)
{
int t=v;
while(f[t]!=)//此语句目的是寻找节点v的根节点
t=f[t];
return t;
}
int krusal()
{
memset(f,,sizeof(f));
int i,root1,root2;
int sum=;
for(i=;i<n;i++)
{
root1=find(edge[i].u);//dege[i].u所在树的根节点
root2=find(edge[i].v);//edge[i].v所在树的根节点
if(root1!=root2)//两棵树的根节点不同，说明edge[i].u和edge[i].v在不同的两棵树上
{
f[root2]=root1;//将两棵树合并成一棵树
sum=sum+edge[i].w;//权值累计
}
}
return sum;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
int i;
for(i=;i<=n-;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[i].u=u;
edge[i].v=v;
edge[i].w=w;
}
qsort(edge,n,sizeof(struct vode),cmp);//用c++的快速排序法根据权值大小从小到大将边排序，注意cmp的使用方法
int sum=krusal();
printf("%d\n",sum);
}
return ;
}
本题还有不明之处：题目限定节点的数目在0~100之间，那么，边的数目就在0~100*99/2=4950之间，为什么我数组开到了5000，甚至7000都不行，开到了8000的时候提交才过，路过的大神若是明白就给我讲解一下吧，小弟不胜感激~