Problem Address：http://poj.org/problem?id=1251
一看就是用Prim算法求最小生成树。
之前已经学过Prim算法，而且这两天刚刚看到，可是还没敲过代码。
所以借此机会学习一下。
重新看了一次，上网找资料什么的，可是虽然是懂了，但就是不知道要怎么写。
n久后决定还是自己试一下才行。
所以敲敲敲……
没想到就这么敲出来了，而且结果还不赖。Debug了一个数据后就过Sample了，一提交，RTE。看了discuss，把scanf和getchar改为了cin，再提交，AC。
很好很强大。
其实Prim算法还是很好理解的，看是实现起来思路可能就有点卡。特别是看着里面说判断是否在某个集合中，所以有点摸不着头脑。
以下贴代码：
#include <iostream>using namespace std;const int MAX = 100000;int V[30], vn;//V用来存放已经访问过的点，vn用于计算V中的个数int n, map[30][30], sum;//map用于存放权值，sum用于计算总路线bool visited[30];//记录是否已访问过void prime(){ int i,j,min,xn; while(vn<n)//如果vn还未到达n则继续寻找下一条边 { min = MAX; for (i=1; i<=vn; i++)//对于V中的每个点搜索 { for (j=1; j<=n; j++)//对于V中每个点的每条邻边进行搜索以找出最小的边 { if (!visited[j]) { if (map[V[i]][j]<min) { min = map[V[i]][j];//记录下最小的边 xn = j;//记录最小边所对应的（不在V中的）点 } } } } visited[xn] = true;//把该点设为已访问 sum += min;//路线值增加 vn++;//V的个数增加 V[vn] = xn;//把该点存入V中 }}int main(){ int i,j,x,y,t; char c; while(cin>>n) { if (n==0) break; for (i=1; i<=n; i++) for (j=1; j<=n; j++) map[i][j] = MAX; for (i=1; i<=n; i++) visited[i] = false; for (i=1; i<n; i++) { cin>>c>>x; y = c - 'A' + 1; for (j=0; j<x; j++) { cin>>c>>t; map[y][c-'A'+1]=t; map[c-'A'+1][y]=t; } } V[1] = 1; visited[1] = true; vn = 1; sum = 0; prime(); cout<<sum<<endl; } return 0;}
p.s.学习算法是辛苦的，同时也是快乐的。这两天掌握了比较多的算法，要好好消化才行~
