#include
<
iostream
>
using
namespace
std;
struct
arr{
int
x,y,c;
}a[
250010
];
int
N,M;
int
len
=
0
;
int
No1,No2;
int
q[
510
];
int
p[
510
];
int
cmp(
const
void
*
no1,
const
void
*
no2){
return
(
*
(arr
*
)no1).c
-
(
*
(arr
*
)no2).c;
}
void
init()
{
scanf(
"
%d%d
"
,
&
N,
&
M);
for
(
int
i
=
1
;i
<=
M;
++
i)
scanf(
"
%d%d%d
"
,
&
a[i].x,
&
a[i].y,
&
a[i].c);
qsort(a
+
1
,M,
sizeof
(arr),cmp);
}
int
Find(
int
x){
if
(x
!=
p[x]) p[x]
=
Find(p[x]);
return
p[x];
}
int
kruskal(
int
ai){
for
(
int
i
=
1
;i
<=
N;
++
i)
p[i]
=
i;
int
k
=
0
,x,y,ans
=
0
;
for
(
int
i
=
1
;i
<=
M;
++
i)
if
(ai
!=
i){
x
=
Find(a[i].x);
y
=
Find(a[i].y);
if
(x
!=
y){
ans
+=
a[i].c;
if
(ai
==
0
)
q[
++
len]
=
i;
k
++
;
if
(k
==
N
-
1
)
return
ans;
p[x]
=
y;
}
}
return
0xFFFFFFF
;
}
int
main()
{
init();
No1
=
kruskal(
0
);
printf(
"
Cost: %d\n
"
,No1);
No2
=
0xFFFFFFF
;
for
(
int
i
=
1
;i
<=
len;
++
i){
int
Min
=
kruskal(q[i]);
if
(No2
>
Min)
No2
=
Min;
}
if
(No2
==
0xFFFFFFF
)
No2
=-
1
;
printf(
"
Cost: %d\n
"
,No2);
return
0
;
}
posted on 2009-06-18 12:23
xfstart07 阅读(194)
评论(0) 编辑 收藏 引用 所属分类:
代码库