Kruskal：1.边排序，2.按边从小到大连接森林至树 3.并查集
#include <stdio.h>
#include <stdlib.h>
#include <memory.h> #define MAXN 27 typedef struct{
int u,v,cost;
}EDGE; int find(int u);
void combine(int u,int v); int cmp(const void *a,const void *b)
{
return ((EDGE *) a) ->cost - ((EDGE *) b) ->cost;
} int pre[MAXN];
EDGE edges[MAXN * MAXN]; int main()
{
int n,cost,cnt,roads;
char u,v; while(scanf("%d",&n) && n){
cnt = ;
for(int i = ;i < n - ;i++){
getchar();
scanf("%c %d",&u,&roads);
for(int i = ;i < roads;i++){
getchar();
scanf("%c %d",&v,&cost);
edges[cnt].u = u - 'A';
edges[cnt].v = v - 'A';
edges[cnt++].cost = cost;
}
} qsort(edges,cnt,sizeof(edges[]),cmp); int sum = ;
memset(pre,-,sizeof(pre));
for(int i = ;i < cnt;i++){
if(find(edges[i].u) != find(edges[i].v)){
sum += edges[i].cost;
combine(edges[i].u,edges[i].v);
}
} printf("%d\n",sum);
}
} int find(int u)
{
while(pre[u] != -){
u = pre[u];
}
return u;
} void combine(int u,int v)
{
int v_header = find(v);
pre[v_header] = u;
}
prim：类似与Dijkstra，把节点分为已扩展和未扩展，为扩展节点中权值最小的节点为下一个扩展节点，Dijkstra中为扩展节点的权值为到起点的最短路径，Prim为到已生成树的最短距离，扩展后更新为扩展节点权值，使用最小堆 O（v + e)，一般直接遍历的权值最小点
#include <stdio.h>
#include <memory.h>
#include <stdlib.h> #define MAXINT 0x7c000000
#define MAXN 30
int map[MAXN][MAXN];
int cost[MAXN],vis[MAXN]; void init(int map[MAXN][MAXN],int n);
int prim(int map[MAXN][MAXN],int n); int main(void)
{
int n; while(scanf("%d",&n) && n){ init(map,n);
char u,v;
int roads,val; for(int i = ;i < n;i++){
getchar();
scanf("%c%d",&u,&roads);
u -= 'A';
for(int j = ;j < roads;j++){
getchar();
scanf("%c%d",&v,&val);
v -= 'A';
map[v][u] = map[u][v] = map[u][v] <
val ? map[u][v] : val;
}
} int res = prim(map,n);
printf("%d\n",res);
} return ;
} void init(int map[MAXN][MAXN],int n)
{
for(int i = ;i < n;i++)
for(int j = ;j < n;j++)
map[i][j] = MAXINT;
} int prim(int map[MAXN][MAXN],int n)
{
for(int i = ;i < n;i++){
vis[i] = ;
cost[i] = MAXINT;
} cost[] = ;
int sum = ; for(int i = ;i < n;i++){ int min,min_val = MAXINT;
for(int j = ;j < n;j++){
if(min_val > cost[j] && !vis[j]){
min_val = cost[j];
min = j;
}
} sum += min_val;
vis[min] = ; for(int j = ;j < n;j++){
cost[j] = cost[j] < map[min][j] ? cost[j] : map[min][j];
}
} return sum;
} //11632756 2014-09-10 21:30:13 Accepted 1301 0MS 200K 1290 B G++