//第一次用kruskal
1
#include<iostream>
2
#include<stdlib.h>
3
#define MAX 100
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
struct Edge
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
int u;
9
int v;
10
int w;
11
};
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13
int parent[MAX]; //全局,感觉不太好
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
int cmp(const void *a, const void *b)
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
17
return (*(Edge*)a).w-(*(Edge*)b).w;
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
int find(int vertex)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
22
if( parent[vertex]<0 )
23
return vertex;
24
else
25
return find(parent[vertex]);
26
}
27![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
28
void Union(int u,int v)
29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
30
int pu=find(u), //parent of u
31
pv=find(v), //parent of v
32
tmp;
33
if (pu != pv)
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
35
tmp = parent[pu] + parent[pv]; //加权合并
36
if (parent[pu] > parent[pv]) //较小的树连接到较大的树后
37![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
38
parent[pu] = pv;
39
parent[pv] = tmp;
40
}
41
else
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
43
parent[pv] = pu;
44
parent[pu] = tmp;
45
}
46
}
47
}
48![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
49
int kruskal(Edge edge[],Edge mst[],int en,int vn)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
51
int i,j,k;
52
j=0;k=0;
53
for(i=0; i<en; i++)
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
55
if( find(edge[i].u) != find(edge[i].v) ) //不属于同一棵树
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
69
int main()
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
71
int vn,i,j,en=0,sum=0;
72
int grap[MAX][MAX];
73![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
74
Edge edge[MAX * MAX];
75
Edge mst [MAX];
76![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
77
while(scanf("%d",&vn)==1)
78![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
79
en=0;
80
sum=0;
81
memset(parent,-1,sizeof(parent)); //makeset
82![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
83
for(i=0;i<vn;i++)
84
for(j=0;j<vn;j++)
85
scanf("%d",&grap[i][j]);
86![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
87
for(i=0;i<vn;i++)
88
for(j=0;j<vn;j++)
89![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i<j)
{ edge[en].u=i;edge[en].v=j; edge[en].w=grap[i][j]; en++; }
90![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
91
qsort(edge,en,sizeof(edge[0]),cmp);
92![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
93
kruskal(edge,mst,en,vn);
94![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
95
for(i=0;i<vn-1;i++)
96
sum+=mst[i].w;
97
cout<<sum<<endl;
98
}
99![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
100
return 0;
101
}
102![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-04-03 01:42
wyiu 阅读(211)
评论(0) 编辑 收藏 引用 所属分类:
POJ