这道题目没有做出来，代码写好之后一直没有AC，本以为做了这么多最小生成树的题目，这道题一定没问题的，结果很遗憾，没有注意细节问题：
首先，如何处理已经建好的路？已经建好的路说明这两个点是连通的，只要把他们间距设为0就好了。
其次，注意循环的控制，我把第一个for中的i=1写成i=0了。
Problem : 1102 ( Constructing Roads ) Judge Status : Accepted
RunId : 5913541 Language : C Author : qq1203456195
Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta
RunId : 5913541 Language : C Author : qq1203456195
Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta
//最小生成树 #include<stdio.h> #define N 1005 #define MAX 9999 int map[N][N],visited[N],close[N],n,q,a,b; int main() { int i,j,nxt,len,nid,flag=1; while(~scanf("%d",&n)) { for(i=0;i<n;i++) { visited[i]=0; for(j=0;j<n;j++) scanf("%d",&map[i][j]); } scanf("%d",&q); for(i=0;i<q;i++) { scanf("%d%d",&a,&b);//ab in tree map[a-1][b-1]=map[b-1][a-1]=0; } visited[0]=1; for(j=0;j<n;j++) close[j]=map[j][0]; len=0; for(i=1;i<n;i++) { nxt=MAX; for(j=0;j<n;j++) { if(!visited[j]&&close[j]<nxt) { nxt=close[j]; nid=j; } } len+=nxt; visited[nid]=1; for(j=0;j<n;j++) { if(!visited[j]&&map[j][nid]<close[j]) close[j]=map[j][nid]; } } printf("%d\n",len); } return 0; }
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/05/08/2489824.html，如需转载请自行联系原作者
