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
];//父節點，深度記錄（這道題沒必要用深度記錄）
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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
