题意梗概：N（n<100）个村子想要富起来，自然就要先修路，不过到底还是没富起来，所以陷入了一个怪圈 ：资金不足->修不起路->资金不足......

为了实现走向全民小康社会，全面实现三个现代化，坚持党的四项......咳咳，总之，你作为一名红领巾，需要提供一种花费最少（即路径最短），又能

让它们各个村庄，都联系起来的修路方法，帮助村民解决困难。

 

问题分析：可以把路径的长短看作权值大小，因此，只需用一些方法村庄图的最小生成树，将权值一一相加就可以得到答案，求最小生成树有很多种方法，

譬如说prim算法或者kruskal算法，这里村庄之间都是相互连通的（没有路0.0），属于稠密图，显然复杂度至于顶点个数有关的prim算法更为合适。

 

1 #include "cstdio" 2 #include "cstring" 3 int v[100][100]; 4 int flag[100]; 5 int prim(int n) 6 { 7     int mi,t=n,k,sum=0; 8     while (--t) 9     {10        mi = 100000;11        for (int i=2;i<=n;i++)12         {13             if (mi > v[1][i] && !flag[i] )14             {15                mi = v[1][i];16                k = i;17             }18         }19         sum += mi;20         flag[k] = 1;21         for (int i=2;i<=n;i++)22         {23            if (v[1][i] > v[k][i] && !flag[i])24                v[1][i] = v[k][i];25         }26     }27     return sum;28 }29 int main()30 {31     int n,a,b,c;32     while (scanf ("%d",&n) && n)33     {34        memset(v,0,sizeof(v));35         for (int j=1;j<=n*(n-1)/2;j++)36         {37             scanf ("%d%d%d",&a,&b,&c);38             v[a][b] = v[b][a] = c;39         }40         memset(flag,0,sizeof(flag));41         printf ("%d\n",prim(n));42     }43     return 0;44 }