| 记录编号 |
39373 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
塔防游戏 |
最终得分 |
100 |
| 用户昵称 |
 zhangchi |
是否通过 |
通过 |
| 代码语言 |
Pascal |
运行时间 |
1.172 s |
| 提交时间 |
2012-07-09 17:54:16 |
内存使用 |
47.88 MiB |
显示代码纯文本
type
node_SPFA=record
v,w,next:longint;
end;
node_SAP=record
v,c,next,un:longint;
end;
var
n,m,s,t,i,j,flow,maxflow,short,tot,head,tail,p,totnum,temp:longint;
found:boolean;
f_SPFA:array[1..1000] of longint;
a_SPFA:array[1..1000000] of node_SPFA;
f_SAP:array[1..1000] of longint;
a_SAP:array[1..2000000] of node_SAP;
h:array[1..1000] of longint;
hnum:array[0..1000] of longint;
q:array[1..1000] of boolean;
d:array[1..1000] of longint;
dis1,dis2:array[1..1000] of longint;
x,y,z:array[1..500000] of longint;
b:array[1..1000] of boolean;
procedure insert_SPFA(x,y,z:longint);
begin
inc(tot);
a_SPFA[tot].next:=f_SPFA[x];
f_SPFA[x]:=tot;
a_SPFA[tot].v:=y;
a_SPFA[tot].w:=z;
end;
procedure insert_SAP(x,y,z:longint);
begin
inc(tot);
a_SAP[tot].next:=f_SAP[x];
f_SAP[x]:=tot;
a_SAP[tot].v:=y;
a_SAP[tot].c:=z;
a_SAP[tot].un:=tot+1;
inc(tot);
a_SAP[tot].next:=f_SAP[y];
f_SAP[y]:=tot;
a_SAP[tot].v:=x;
a_SAP[tot].c:=0;
a_SAP[tot].un:=tot-1;
end;
procedure SPFA1;
begin
head:=0; tail:=1;
fillchar(dis1,sizeof(dis1),$7F div 3);
fillchar(q,sizeof(q),false);
dis1[s]:=0;
d[1]:=s;
repeat
head:=head mod n+1;
temp:=d[head];
q[temp]:=false;
p:=f_SPFA[temp];
while p<>0 do
begin
if dis1[temp]+a_SPFA[p].w<dis1[a_SPFA[p].v] then
begin
dis1[a_SPFA[p].v]:=dis1[temp]+a_SPFA[p].w;
if q[a_SPFA[p].v]=false then
begin
q[a_SPFA[p].v]:=true;
if dis1[a_SPFA[p].v]<dis1[head mod n+1] then
begin
d[head]:=a_SPFA[p].v;
head:=head mod n-1;
if head<=0 then head:=head+n;
end
else
begin
tail:=tail mod n+1;
d[tail]:=a_SPFA[p].v;
end;
end;
end;
p:=a_SPFA[p].next;
end;
until head=tail;
end;
procedure SPFA2;
begin
head:=0; tail:=1;
fillchar(dis2,sizeof(dis2),$7F div 3);
fillchar(q,sizeof(q),false);
dis2[t]:=0;
d[1]:=t;
repeat
head:=head mod n+1;
temp:=d[head];
q[temp]:=false;
p:=f_SPFA[temp];
while p<>0 do
begin
if dis2[temp]+a_SPFA[p].w<dis2[a_SPFA[p].v] then
begin
dis2[a_SPFA[p].v]:=dis2[temp]+a_SPFA[p].w;
if q[a_SPFA[p].v]=false then
begin
q[a_SPFA[p].v]:=true;
if dis2[a_SPFA[p].v]<dis2[head mod n+1] then
begin
d[head]:=a_SPFA[p].v;
head:=head mod n-1;
if head<=0 then head:=head+n;
end
else
begin
tail:=tail mod n+1;
d[tail]:=a_SPFA[p].v;
end;
end;
end;
p:=a_SPFA[p].next;
end;
until head=tail;
end;
procedure SAP(x:longint);
var
p,temp,minh:longint;
begin
if x=t then
begin
inc(maxflow,flow);
found:=true;
exit;
end;
temp:=flow;
minh:=totnum-1;
p:=f_SAP[x];
while p<>0 do
begin
if a_SAP[p].c>0 then
begin
if h[a_SAP[p].v]+1=h[x] then
begin
if a_SAP[p].c<flow then flow:=a_SAP[p].c;
SAP(a_SAP[p].v);
if h[s]>=totnum then exit;
if found then break;
flow:=temp;
end;
if h[a_SAP[p].v]<minh then minh:=h[a_SAP[p].v];
end;
p:=a_SAP[p].next;
end;
if not found then
begin
dec(hnum[h[x]]);
if hnum[h[x]]=0 then h[s]:=totnum;
h[x]:=minh+1;
inc(hnum[h[x]]);
end
else
begin
dec(a_SAP[p].c,flow);
inc(a_SAP[a_SAP[p].un].c,flow);
end;
end;
begin
assign(input,'defence.in'); reset(input);
assign(output,'defence.out'); rewrite(output);
readln(n,m,s,t);
for i:=1 to m do
begin
readln(x[i],y[i],z[i]);
insert_SPFA(x[i],y[i],z[i]);
insert_SPFA(y[i],x[i],z[i]);
end;
SPFA1;
SPFA2;
short:=dis1[t];
tot:=0;
for i:=1 to m do
begin
if (dis1[x[i]]+dis2[y[i]]+z[i]=short)or(dis2[x[i]]+dis1[y[i]]+z[i]=short) then
begin
if b[x[i]]=false then
begin
b[x[i]]:=true;
inc(totnum);
end;
if b[y[i]]=false then
begin
b[y[i]]:=true;
inc(totnum);
end;
if dis1[x[i]]+dis2[y[i]]+z[i]=short then
insert_SAP(x[i],y[i],1);
if dis2[x[i]]+dis1[y[i]]+z[i]=short then
insert_SAP(y[i],x[i],1);
end;
end;
hnum[0]:=totnum;
while h[s]<totnum do
begin
flow:=maxlongint div 2;
found:=false;
SAP(s);
end;
writeln(maxflow);
close(input); close(output);
end.