NKRACING - Vòng đua F1

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program NKRACING;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxe = 1000000;
var
  n,e: integer;
  u,v,cost: array[1..maxe] of integer;
  pr,rank: array[1..maxn] of integer;
  tot,tree: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n, e);
  tot := 0;
  for i := 1 to e do
    begin
      readln(f, u[i], v[i], cost[i]);
      tot := tot + cost[i];
    end;

  close(f);
end;

procedure sw(var x,y: integer);
var
  z: integer;
begin
  z := x;  x := y;  y := z;
end;

procedure swap(i,j: integer);
begin
  sw(u[i],u[j]);  sw(v[i],v[j]);  sw(cost[i],cost[j]);
end;

procedure sort(l,h: integer);
var
  i,j,p: integer;
begin
  if l >= h then exit;
  i := l;  j := h;  p := cost[random(h - l + 1) + l];

  repeat
    while cost[i] > p do inc(i);
    while cost[j] < p do dec(j);
    if i <= j then
      begin
        if i < j then swap(i,j);
        inc(i);  dec(j);
      end;
  until i > j;

  sort(l,j);  sort(i,h);
end;

function root(x: integer): integer;
begin
  if x <> pr[x] then pr[x] := root(pr[x]);
  root := pr[x];
end;

procedure link(x,y: integer);
begin
  if rank[x] > rank[y] then pr[y] := x else pr[x] := y;
  if rank[x] = rank[y] then inc(rank[y]);
end;

procedure solve;
var
  i,nedge: integer;
begin
  tree := 0;
  for i := 1 to n do
    begin
      pr[i] := i;
      rank[i] := 0;
    end;

  nedge := 0;
  for i := 1 to e do
    if root(u[i]) <> root(v[i]) then
      begin
        tree := tree + cost[i];
        inc(nedge);
        link(root(u[i]),root(v[i]));
      end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, tot - tree);
  close(f);
end;

begin
  init;
  sort(1,e);
  solve;
  printresult;
end.

Download