典型的最小生成树算法，题目给出图的邻接矩阵，要求输出最小生成树对应的权值和，本例用prim算法实现。
对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。有两种非常典型的算法：Prim算法和kruskal算法，这两种算法都采用了贪心策略。
Prim算法的基本思想是：
(1) 在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U={v0}，集合T(E)为空。
(2) 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1}，同时将该边加入集合T(E)中。
(3) 重复(2)，直到U = V为止。
这时T(E)中有n-1条边，T=(U,T(E))就是一棵最小生成树。
在本例中，由于各个点都是用字符串表示，而不是数字可以直接加入到邻接矩阵中，所以需要将字符串映射为数字，由于题目中有很多点，为了提高效率，用二叉查找树来进行查找，具体的使用方法请参见另一篇解题报告：Pku acm 2503 Babelfish 查找算法总结(一) ----二叉查找数(BST)，将2503，1258的代码拼接起来即使本题的代码。
数组origin存放原始数据，max_distance存放矩阵中的最大值，sum存放最小生成树的sum，opt存放节点和最小生成树之间的最小距离,flag
判断是否已经加入到最小生成树中，首先将1号顶点加入最小生成树中，flag[1]
为true，其他为false，opt[i]的值为origin[1][i]的值，然后选择不在最小
生成树中的最小边i，然后加入到最小生成树中，另外更新opt[i],flag[i]。如
此反复，直到取到v-1条边为止。
带有详细注释的代码可以从http://download.csdn.net/user/china8848/获得。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/china8848/archive/2008/03/31/2234161.aspx