type TEdge = record start, terminal: longint; weight: int64; end; TEdgeArr = array of TEdge;
operator <(e1, e2: TEdge)res: boolean; begin res := e1.weight < e2.weight; end;
operator >(e1, e2: TEdge)res: Boolean; begin res := e1.weight > e2.weight; end;
procedure SortEdge(A: TEdgeArr; l, r: longint); var i, j: longint; t, m: TEdge; begin i := l; j := r; m := A[(i+j) >> 1]; repeat while A[i]<m do inc(i); while A[j]>m do dec(j); if i<=j then begin t := A[i]; A[i] := A[j]; A[j] := t; inc(i); dec(j); end; until i>j; if i<r then SortEdge(A, i, r); if l<j then SortEdge(A, l, j); end;
const INF: int64 = 1<<60 div 3; var map: array [1..100, 1..100] of int64; n, i, j: longint;
function prim(x: longint): int64;
var lowest: array [1..100] of int64; visited: array [1..100] of boolean; min: int64; i, j, minindex: longint; begin fillchar(visited, sizeof(visited), 0); visited[x] := true;
for i := 1 to n do lowest[i] := map[i, x];
prim := 0; for i := 2 to n do begin min := INF;
for j := 1 to n do if (not visited[j]) and (min > lowest[j]) then begin min := lowest[j]; minindex := j; end; visited[minindex] := true; prim := prim + min;
for j := 1 to n do begin if visited[j] then continue; if map[j, minindex] < lowest[j] then lowest[j] := map[j, minindex]; end; end; end;
function Kruscal: int64; var Edges: TEdgeArr; UnionSet: array [0..100] of longint; i: longint;
procedure InitEdges; var i, j: longint; E: TEdge; begin for i := 1 to n do for j := 1 to i-1 do begin E.start := i; E.terminal := j; E.weight := map[i, j]; SetLength(Edges, Length(Edges)+1); Edges[High(Edges)] := E; end; SortEdge(Edges, Low(Edges), High(Edges)); end;
function Find(x: longint): longint; var root: longint; begin root := x; while root <> UnionSet[root] do root := UnionSet[root]; UnionSet[x] := root; exit(root); end;
function Union(x, y: longint): boolean; var px, py: longint; begin px := Find(x); py := Find(y); if px = py then exit(False); UnionSet[px] := py; exit(True); end;
begin Kruscal := 0; fillchar(UnionSet, sizeof(UnionSet), 0); InitEdges; for i := 1 to n do UnionSet[i] := i; for i := Low(Edges) to High(Edges) do if Union(Edges[i].start, Edges[i].terminal) then begin Kruscal := Kruscal + Edges[i].weight; end; end;
begin assign(input, 'main.in'); reset(input); assign(output, 'main.out'); rewrite(output);
readln(n); for i := 1 to n do for j := 1 to n do read(map[i, j]); writeln(Kruscal);
close(input); close(output); end.
|
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.