CHEER - Động viên đàn bò

Tác giả: ll931110

Ngôn ngữ: Pascal

program CHEER;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxp = 100000;
type
  edge = record
    u,v,cost: longint;
  end;
var
  e: array[1..maxp] of edge;
  a,pr,rank: array[1..maxn] of longint;
  n,p: longint;
  res: longint;

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

  readln(f, n, p);
  for i := 1 to n do read(f, a[i]);

  for i := 1 to p do
    begin
      read(f, e[i].u, e[i].v, e[i].cost);
      e[i].cost := 2 * e[i].cost + a[e[i].u] + a[e[i].v];
    end;

  close(f);
end;

procedure swap(var x,y: edge);
var
  z: edge;
begin
  z := x;  x := y;  y := z;
end;

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

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

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

procedure makeset(i: longint);
begin
  pr[i] := i;
  rank[i] := 0;
end;

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

procedure link(x,y: longint);
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 union(x,y: longint);
begin
  link(root(x),root(y));
end;

procedure Kruskal;
var
  i,cc: longint;
begin
  cc := 0;
  res := 0;
  for i := 1 to n do
    if (res = 0) or (res > a[i]) then res := a[i];

  for i := 1 to n do makeset(i);

  for i := 1 to p do
    begin
      if cc = n - 1 then break;
      if root(e[i].u) <> root(e[i].v) then
        begin
          res := res + e[i].cost;
          union(e[i].u,e[i].v);
          inc(cc);
        end;
    end;
end;

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

begin
  init;
  sort(1,p);
  Kruskal;
  printresult;
end.

Download