- Kerry 的电缆网络
- 2010-07-05 21:53:10 @
var a, b, father : array[1..10000] of longint;
t : array[1..10000] of real;
n, e, p, i : longint;
ans, s : real;
procedure inst;
var i : longint;
begin
assign(input, 'P.in');
assign(output, 'P.out');
reset(input);
rewrite(output);
readln(s);
readln(n);
while not eof do
begin
readln(a[i], b[i], t[i]);
inc(e);
end;
if e < n - 1 then begin writeln('Impossible'); halt; end;
end;
procedure swap(var a, b : longint);
var temp : longint;
begin
temp := a;
a := b;
b := temp;
end;
procedure swap1(var a, b : real);
var temp : real;
begin
temp := a;
a := b;
b := temp;
end;
procedure qsort(l, r : longint);
var i, j : longint;
mid : real;
begin
i := l;
j := r;
mid := t[((i + j) div 2)];
repeat
while t[i] < mid do inc(i);
while t[j] > mid do dec(j);
if i j;
if j > l then qsort(l, j);
if r > i then qsort(i, r);
end;
function getfather(x : longint) : longint;
begin
if x = father[x] then exit(x);
father[x] := getfather(father[x]);
exit(father[x]);
end;
begin
inst;
qsort(1, e);
for i := 1 to n do
father[i] := i;
p := 1;
ans := 0;
for i := 1 to e do
begin
if getfather(a[i]) getfather(b[i])
then
begin
ans := ans + t[i];
father[getfather(b[i])] := a[i];
inc(p);
if p = n then break;
end;
end;
if ans