Time Limit:
1000MS????
Memory Limit:
32768KB????
64bit IO Format:
%I64d & %I64u
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
];//父節(jié)點(diǎn)，深度記錄（這道題沒必要用深度記錄）
7
//
int
max1;
8
struct
Line{
9
int
first;
10
int
last;
11
int
cost;
12
}line[
50000
];//還沒學(xué)會(huì)用數(shù)組來記錄邊，還是在用結(jié)構(gòu)體做的，編程風(fēng)格有待提高
13
int
cmp(Line a,Line b){
return
a.cost<
b.cost;}//排序的依據(jù)函數(shù)
14
int
find(
int
x)//找點(diǎn)的父節(jié)點(diǎn)，把一條邊的點(diǎn)搞到一個(gè)集合里面
15
{
16
if
(father[x]!=
x)
17
{
18
father[x]=
find(father[x]);//這里有個(gè)優(yōu)化，不會(huì)出現(xiàn)長鏈的情況，直接把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
;//如果是同一個(gè)父親節(jié)點(diǎn)的，return false;
26
else
{
27
father[b1]=
a1;//否則合并成一個(gè)集合
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
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
