*本题的Kruskal解法http://blog.csdn.net/sm9sun/article/details/53257264
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1301
题目描述：
给定村庄数n，用字母表的前n个字母表示，接下来n-1行每行一个村庄字母和与其连接的村庄数以及各村庄的字母和距离。求最小生成树。
解题思路：
先说明一下prim算法：
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小
我们假设5个点A,B,C,D,E 其互相的关系（边的权值）为以下矩阵（二维数组），然后简单写几个边
Side（A,B）=Side（B,A）=1 //AB的边权值 为1 prim适用于无向图，所以记得双向赋值
Side（A,C）=Side（C,A）=2
Side（A,E）=Side（E,A）=5
Side（B,E）=Side（B,A）=3
Side（C,D）=Side（D,C）=4
我们填充一下数组，因为求最小的生成树，所以本身（A,A）我们设为0，没有连接的我们设为M（MAX）
| A | B | C | D | E | |
| A | 0 | 1 | 2 | M | 5 |
| B | 1 | 0 | M | M | 3 |
| C | 2 | M | 0 | 4 | M |
| D | M | M | 4 | 0 | M |
| E | 5 | 3 | M | M | 0 |
我们看一下如何连通这些点，首先以第一个为起点（反正所有的点我们都要连接）
与A最近的点即B，我们可以这样想，如果其他的点都连接起来了，那么肯定也是以AB边去连接A，所以AB边必不可少。
当AB连接了之后，我们将B与其他点的状态与A共享,也就是，原来A连接不到的（或权值较大的），可以通过B作为桥梁去连接。
我们刷新一下该数组
| A | B | C | D | E | |
| A | 0 | 1 | 2 | M | 3 |
| B | 1 | 0 | M | M | 3 |
| C | 2 | M | 0 | 4 | M |
| D | M | M | 4 | 0 | M |
| E | 3 | 3 | M | M | 0 |
我们看到，AE的边 发生了变化，因为原有的AE=5权值大于AB，所以当我们选择连接E的时候，我们更倾向于通过B连接，也就等同于A连接。
或者我们可以把A看作（A,B）集合。然后我们再找与其边最小的点(C)
| A | B | C | D | E | |
| A | 0 | 1 | 2 | 4 | 3 |
| B | 1 | 0 | M | M | 3 |
| C | 2 | M | 0 | 4 | M |
| D | 4 | M | 4 | 0 | M |
| E | 3 | 3 | M | M | 0 |
然后连接E，最后D。
所以我们的操作实际上就是不断的刷新维护第一列（行）数组。当然，为了清晰，我们也可以把其单独摘出来，或者用队列记录这一个集合等处理方式
#include<stdio.h>#include<string.h>#define INF 99999999int V_nMapValue[30][30];int V_nMinAns;int n;int fmin(int a,int b) { return a<b?a:b;}void Init() //初始化{ int i,j;for(i=0;i<30;i++)for(j=0;j<30;j++)V_nMapValue[i][j]=(i==j)?0:INF;V_nMinAns=0;}int Get_PointId_by_PointName(char c){ return int(c-64);}void Prim(){ int Z_vis[30], i,j,k;memset(Z_vis, 0, sizeof(Z_vis));Z_vis[1]=1; //这里用Z数组标记该节点是否已经进入集合 for(i=2;i<=n;i++) { int Id_temp=0,Value_temp=INF; for(j=2;j<=n;j++) if(!Z_vis[j]&&V_nMapValue[1][j]<Value_temp){Id_temp=j;Value_temp=V_nMapValue[1][j];}if(Value_temp==INF) break; V_nMinAns+=Value_temp; Z_vis[Id_temp]=1; // printf("%d~~%d~~%d\n",Id_temp,Value_temp,V_nMinAns); for(k=2;k<=n;k++)if(!Z_vis[k])V_nMapValue[1][k]=fmin(V_nMapValue[1][k],V_nMapValue[Id_temp][k]);// for(j=1;j<=n;j++)// printf("%d%c",V_nMapValue[1][j],j==n?'\n':' '); }} int main(){ char N_cStPoint,N_cEnPoint_temp;int C_nListSum; int V_nSide_temp;int Point_St_id,Point_En_id;while(scanf("%d",&n)!=EOF&&n){getchar();Init();for(int i=1;i<n;i++){scanf("%c", &N_cStPoint);scanf("%d", &C_nListSum);while(C_nListSum--){getchar();scanf("%c", &N_cEnPoint_temp);scanf("%d", &V_nSide_temp);Point_St_id=Get_PointId_by_PointName(N_cStPoint);Point_En_id=Get_PointId_by_PointName(N_cEnPoint_temp);V_nMapValue[Point_St_id][Point_En_id]=V_nMapValue[Point_En_id][Point_St_id]=V_nSide_temp;}getchar();}/*for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)printf("%d%c",V_nMapValue[i][j],j==n?'\n':' ');*/Prim();printf("%d\n",V_nMinAns);}return 0;}