题目：
省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
Output对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
Sample Output
3
?
题意描述：
输入道路条数和城市数目
计算并输出使任意两个村庄直接或者间接连通的最短距离
解题思路：
属于最小生成树问题，按照数据格式，使用Kruskal算法即可。
代码实现：
#include<stdio.h>
#include<string.h>
int e[][],book[],dis[];
const int inf=;
int main()
{
int n,m,min,t1,t2,t3,i,j,c,sum,k;
while(scanf("%d%d",&m,&n), m != )//m为道路条数，n为村庄个数
{
memset(e,,sizeof(e));
for(i=;i<=n;i++)//初始化邻接矩阵
{
for(j=;j<=n;j++){
if(i==j)
e[i][j]=;
else
e[i][j]=inf;
}
}
for(i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
e[t1][t2]=t3;
e[t2][t1]=t3;
}
for(i=;i<=n;i++)//初始化dis，存储距离生成树(仅有1顶点）到每个非树顶点的距离
dis[i]=e[][i];
memset(book,,sizeof(book));
book[]=;
c=;
sum=;//sum初始化，当只有一个正确样例时注意多复制一下 while(c < n)//直到找到n-1条边
{
min=inf;
for(j=,i=;i<=n;i++)
{//遍历每个定点，找到某个顶点没有被用过而且距离生成树又最近
if(book[i]== && dis[i] < min)
{
min=dis[i];
j=i;
}
}
book[j]=;//标记使用并计数，将其累加到sum上
c++;
sum += dis[j]; for(k=;k<=n;k++)
{//最后遍历所有边，以j为中间点更新dis数组中生成树到每一个非树顶点的距离
if(book[k]== && dis[k] > e[j][k])
dis[k]=e[j][k];
}
} for(i=;i<=n;i++){
if(!book[i])
break;
}
if(i == n+)
printf("%d\n",sum);
else
printf("?\n");
}
return ;
}
易错分析：
1、注意数据输入，结点数在前还是边数在前
2、当只有一个样例时，多出几组测试样例，想几个样例的时间跟罚时20分钟比起来要少的多，另外不影响情绪