存两个图论模板

Posted by Cww97 on 2016-01-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50475016
kruskal
模板题 codevs1078
http://codevs.cn/problem/1078/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
{
作者:CWW970329
题目:p1078 最小生成树
}

program cx;
var i,j,n,cnt,sum,top:longint;
home,ax,ay,aw:array[0..100000]of longint;
g:array[0..200,0..200]of longint;

procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l; j:=r;
x:=aw[(l+r)>>1];
repeat
while aw[i]<x do inc(i);
while x<aw[j] do dec(j);
if not(i>j) then
begin
y:=aw[i]; aw[i]:=aw[j]; aw[j]:=y;
y:=ax[i]; ax[i]:=ax[j]; ax[j]:=y;
y:=ay[i]; ay[i]:=ay[j]; ay[j]:=y;
inc(i); j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

function find(x:longint):longint;
begin
if home[x]=x then exit(x);
home[x]:=find(home[x]);
exit(home[x]);
end;

begin
read(n);
for i:=1 to n do
for j:=1 to n do read(g[i,j]);
for i:=2 to n do
for j:=1 to i-1 do
begin
inc(cnt);
ax[cnt]:=i;
ay[cnt]:=j;
aw[cnt]:=g[i,j];
end;
sort(1,cnt);
for i:=1 to n do home[i]:=i;
for i:=1 to cnt do
begin
if find(ax[i])=find(ay[i]) then continue;
home[find(ax[i])]:=find(ay[i]);
inc(sum,aw[i]);
inc(top);
if top=n-1 then break;
end;
writeln(sum);
end.

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
program cx;
type node=record
x,y:longint; end;
const big=999999999;
var i,m,n,s,o,x,y,cnt,r,f:longint;
a:array[0..100000]of node;
q,e,next,head:array[0..100000]of longint;
w,dist:array[0..100000]of real;
v:array[0..100000]of boolean;

procedure build(x,y:longint);
begin
inc(cnt);
e[cnt]:=y;
next[cnt]:=head[x];
head[x]:=cnt;
w[cnt]:=sqrt(sqr(a[x].x-a[y].x)+
sqr(a[x].y-a[y].y));
end;

procedure spfa;
var i,p:longint;
begin
f:=1;
r:=1;
q[1]:=s;
v[s]:=true;
dist[s]:=0;
while f<=r do
begin
p:=head[q[f]];
while p>0 do
begin
if dist[q[f]]+w[p]<dist[e[p]] then
begin
dist[e[p]]:=dist[q[f]]+w[p];
if not v[e[p]] then
begin
inc(r);
q[r]:=e[p];
v[e[p]]:=true;
end;
end;
p:=next[p];
end;
inc(f);
v[q[f]]:=false;
end;
end;

begin
assign(input,'short.in'); reset(input);
assign(output,'short.out');rewrite(output);
fillchar(v,sizeof(v),false);
cnt:=0;
read(n);
for i:=1 to n do read(a[i].x,a[i].y);
for i:=1 to n do dist[i]:=big;
read(m);
for i:=1 to m do
begin
read(x,y);
build(x,y);
build(y,x);
end;
read(s,o);
spfa;
writeln(dist[o]:0:2);
close(input);
close(output);
end.