Ice_cream’s world III
?????????????????????????????????????????????????? Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)?????????????????????????????????????????????????????????????????????????????? Total Submission(s): 1146????Accepted Submission(s): 379
Problem 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
?
Author
Wiskey
?
Source
?
Recommend
?
//并查集實現克魯斯卡爾；
1
#include <stdio.h>
2
#include <algorithm>
3
using
namespace
std;
4
int
father[
1010
] ;
5
6
struct
rode
7
{
8
int
a, b ,c;
9
};
10
rode num[
10010
];
11
12
bool
cmp(rode a, rode b)
13
{
14
return
a.c <
b.c ;
15
}
16
17
int
find(
int
a)
18
{
19
while
(a !=
father[a])
20
a =
father[a];
21
return
a;
22
}
23
24
void
mercy(
int
a,
int
b)
25
{
26
int
q =
find(a);
27
int
p =
find(b);
28
if
(q !=
p)
29
father[q] =
p;
30
31
}
32
33
int
main()
34
{
35
int
i, n, m;
36
while
(~scanf(
"
%d %d
"
, &n, &
m))
37
{
38
for
(i=
0
; i<n; i++
)
39
father[i] =
i;
40
for
(i=
0
; i<m; i++
)
41
scanf(
"
%d %d %d
"
,&num[i].a, &num[i].b, &
num[i].c);
42
sort(num, num+
m, cmp);
43
int
total =
0
;
44
for
(i=
0
; i<m; i++
)
45
{
46
//
mercy(num[i].a, num[i].b);
47
if
(find(num[i].a) ==
find(num[i].b))
48
continue
;
49
else
50
{
51
//
printf("1\n");
52
total +=
num[i].c;
53
mercy(num[i].a, num[i].b) ;
54
}
55
}
56
int
ac =
0
;
57
for
(i=
0
; i<n; i++
)
58
{
59
if
(father[i] ==
i)
60
ac++
;
61
}
62
if
(ac ==
1
)
63
printf(
"
%d\n\n
"
, total);
64
else
65
printf(
"
impossible\n\n
"
);
66
}
67
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
