//第一次用kruskal
1
#include<iostream>
2#include<stdlib.h>
3#define MAX 100
4using namespace std;
5
6struct Edge
7
{
8
int u;
9 int v;
10 int w;
11
};
12
13int parent[MAX]; //全局,感覺不太好
14
15int cmp(const void *a, const void *b)
16{
17 return (*(Edge*)a).w-(*(Edge*)b).w;
18}
19
20int find(int vertex)
21{
22 if( parent[vertex]<0 )
23 return vertex;
24 else
25 return find(parent[vertex]);
26}
27
28void Union(int u,int v)
29{
30 int pu=find(u), //parent of u
31 pv=find(v), //parent of v
32 tmp;
33 if (pu != pv)
34
{
35 tmp = parent[pu] + parent[pv]; //加權合并
36 if (parent[pu] > parent[pv]) //較小的樹連接到較大的樹后
37 {
38 parent[pu] = pv;
39 parent[pv] = tmp;
40
}
41 else
42 {
43 parent[pv] = pu;
44 parent[pu] = tmp;
45 }
46 }
47}
48
49int kruskal(Edge edge[],Edge mst[],int en,int vn)
50{
51 int i,j,k;
52 j=0;k=0;
53 for(i=0; i<en; i++)
54 {
55 if( find(edge[i].u) != find(edge[i].v) ) //不屬于同一棵樹
56 {
57 mst[j].u=edge[i].u;
58 mst[j].v=edge[i].v;
59 mst[j].w=edge[i].w;
60 j++;
61 k+=edge[i].w;
62 Union(edge[i].u, edge[i].v);
63 }
64 if(j== vn-1) break;
65 }
66 return k;
67}
68
69int main()
70{
71 int vn,i,j,en=0,sum=0;
72 int grap[MAX][MAX];
73
74 Edge edge[MAX * MAX];
75 Edge mst [MAX];
76
77 while(scanf("%d",&vn)==1)
78 {
79 en=0;
80 sum=0;
81 memset(parent,-1,sizeof(parent)); //makeset
82
83 for(i=0;i<vn;i++)
84 for(j=0;j<vn;j++)
85 scanf("%d",&grap[i][j]);
86
87 for(i=0;i<vn;i++)
88 for(j=0;j<vn;j++)
89 if(i<j) { edge[en].u=i;edge[en].v=j; edge[en].w=grap[i][j]; en++; }
90
91 qsort(edge,en,sizeof(edge[0]),cmp);
92
93 kruskal(edge,mst,en,vn);
94
95 for(i=0;i<vn-1;i++)
96 sum+=mst[i].w;
97 cout<<sum<<endl;
98 }
99
100 return 0;
101}
102
posted on 2009-04-03 01:42
wyiu 閱讀(236)
評論(0) 編輯 收藏 引用 所屬分類:
POJ