Description
ice_cream’s world becomes stronger and stronger; every road is built as undirected. The queen enjoys traveling around her world; the queen’s requirement is like II problem, beautifies the roads, by which there are some ways from every city to the capital. The project’s cost should be as less as better.
Input
Every case have two integers N and M (N<=1000, M<=10000) meaning N cities and M roads, the cities numbered 0…N-1, following N lines, each line contain three integers S, T and C, meaning S connected with T have a road will cost C.
Output
If Wiskey can’t satisfy the queen’s requirement, you must be output “impossible”, otherwise, print the minimum cost in this project. After every case print one blank.
Sample Input
2 1 0 1 10 4 0
Sample Output
10 impossible
简单的最小生成树问题，用并查集来做。
1
#include<cstdio>
2
#include<
string
.h>
3
#include<algorithm>
4
using
namespace
std;
5
int
ans;
6
int
father[
2000
],rank[
2000
];//父节点，深度记录（这道题没必要用深度记录）
7
//
int
max1;
8
struct
Line{
9
int
first;
10
int
last;
11
int
cost;
12
}line[
50000
];//还没学会用数组来记录边，还是在用结构体做的，编程风格有待提高
13
int
cmp(Line a,Line b){
return
a.cost<
b.cost;}//排序的依据函数
14
int
find(
int
x)//找点的父节点，把一条边的点搞到一个集合里面
15
{
16
if
(father[x]!=
x)
17
{
18
father[x]=
find(father[x]);//这里有个优化，不会出现长链的情况，直接把father[x]=find[father[x]];
19
}
20
return
father[x];
21
}
22
bool
Union(
int
a,
int
b)//合并集合
23
{
24
int
a1=find(a),b1=
find(b);
25
if
(a1==b1)
return
false
;//如果是同一个父亲节点的，return false;
26
else
{
27
father[b1]=
a1;//否则合并成一个集合
28
ans++
;
29
rank[a1]+=
rank[b1];
30
if
(max1<rank[a1]) max1=
rank[a1];
31
return
true
;
32
}
33
}
34
35
36
int
main()
37
{
38
int
a,b,c,n,m;
39
while
(scanf(
"
%d%d
"
,&n,&m)!=
EOF)
40
{
41
for
(
int
i=
0
;i<n;i++
)
42
{
43
father[i]=
i;
44
rank[i]=
1
;
45
}
46
for
(
int
i=
1
;i<=m;i++
)
47
{
48
scanf(
"
%d %d %d
"
,&a,&b,&
c);
49
line[i].first=
a;
50
line[i].last=
b;
51
line[i].cost=
c;
52
53
}
54
sort(line+
1
,line+m+
1
,cmp);
55
max1=
0
;
56
int
sum=
0
;
57
ans=
0
;
58
for
(
int
i=
1
;i<=m;i++
)
59
{
60
if
(Union(line[i].first,line[i].last))
61
sum+=
line[i].cost;
62
}
63
if
(ans==n-
1
) printf(
"
%d\n
"
,sum);
64
else
printf(
"
impossible\n
"
);
65
printf(
"
\n
"
);
66
}
67
return
0
;
68
}
