题目链接：

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 26151    Accepted Submission(s): 11660

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

 

 

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

 

 

Output

对每个测试用例，在1行里输出最小的公路总长度。

 

 

Sample Input

3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

 

 

Sample Output

3 5

 

 

这是一个简单的最小生成树，第一次做，没有深刻的理解，自我感觉和dijkstra没有什么太大的本质区别，总之又是一种找最短路的很好的方法吧，值得参考~

 

1 #include 
       
         2 #include 
        
          3 using namespace std; 4 int node[110],map[110][110],n; 5 const int INF=9999999; 6  7 void prim() 8 { 9     int vis[110]= {
     0};10     int sum=0,Min,tm=1,m;11     node[tm]=0;12     vis[tm]=1;//cout<
         
          <
          
           map[tm][i])21                     node[i]=map[tm][i];22                 if (Min>node[i])23                 {24                     Min=node[i];25                     m=i;26                 }27             }28         vis[m]=1;29         sum+=Min;30         tm=m;31     }32     printf ("%d\n",sum);33 }34 35 int main ()36 {37     while (cin>>n&&n)38     {39         for(int i=1; i<=n; i++)40         {41             node[i]=INF;42         }43         for (int i=1; i<=n*(n-1)/2; i++)44         {45             int a,b,c;46             cin>>a>>b>>c;47                 map[a][b]=map[b][a]=c;48         }49         prim();50     }51     return 0;52 }
          
         
        
       

 第二种方法哈，也就是并查集+最小生成树了~~哇哈哈

详见代码。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5 int father[110],sum; 6 struct node 7 { 8     int s,d,f; 9 } p[5010];10 11 bool cmp(const node &a,const node &b)12 {13     return a.f
          
           >n&&n)44     {45         sum=0;46         set(n);47         for (int i=1; i<=n*(n-1)/2; i++)48             cin>>p[i].s>>p[i].d>>p[i].f;49         sort(p+1,p+n*(n-1)/2+1,cmp);50         for (int i=1; i<=n*(n-1)/2; i++)51         {52             Union(p[i].s,p[i].d,p[i].f);53         }54         printf ("%d\n",sum);55     }56     return 0;57 }