讨论 / 两次spfa+前向星优化空间+卡时 很长的代码130行+
lifei 2012-07-31 08:04:00
点我顶贴 收藏 删除
测试结果1: 通过本测试点|有效耗时172ms

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时188ms

测试结果4: 通过本测试点|有效耗时453ms

测试结果5: 通过本测试点|有效耗时437ms

测试结果6: 通过本测试点|有效耗时203ms

测试结果7: 通过本测试点|有效耗时204ms

测试结果8: 通过本测试点|有效耗时312ms

测试结果9: 通过本测试点|有效耗时500ms

测试结果10: 通过本测试点|有效耗时469ms

var x,y:array[0..1000001]of longint;

w,f,d1,d2,q:array[0..100001]of longint;

flag:array[0..100001]of boolean;

n,m,z,e:longint;

function fmin(a,b:longint):longint;

begin if a<b then exit(a);exit(b);end;

function fmax(a,b:longint):longint;

begin if a>b then exit(a);exit(b);end;

procedure swap(var a,b:longint);

var t:longint;

begin t:=a;a:=b;b:=t;end;

procedure qs(l,r:longint);

var i,j,m:longint;

begin

i:=l;j:=r;m:=x[(l+r)div 2];

repeat

while x[i]<m do inc(i);

while x[j]>m do dec(j);

if i<=j then

begin

swap(x[i],x[j]);

swap(y[i],y[j]);

inc(i);dec(j);

end;

until i>j;

if i<r then qs(i,r);

if l<j then qs(l,j);

end;

procedure init;

var i:longint;

begin

readln(n,m);

for i:=1 to n do read(w[i]);

readln;

e:=0;

for i:=1 to m do

begin

inc(e);

readln(x[e],y[e],z);

if z=2 then begin inc(e);x[e]:=y[e-1];y[e]:=x[e-1];end;

end;

end;

procedure spfa1;

var i,h,t,v,u,o,ww:longint;

begin

qs(1,e);

fillchar(f,sizeof(f),0);

for i:=1 to e do

if f[x[i]]=0 then f[x[i]]:=i;

f[n+1]:=e+1;

for i:=n downto 1 do

if f[i]=0 then f[i]:=f[i+1];

for i:=1 to n do d1[i]:=200;

fillchar(flag,sizeof(flag),false);

fillchar(q,sizeof(q),0);

h:=0;t:=1;q[t]:=1;flag[1]:=true;d1[1]:=w[1];o:=0;

while h<>t do

begin

h:=(h mod 100000)+1;

v:=q[h];

flag[v]:=false;

if f[v]<>0 then

for i:=f[v] to f[v+1]-1 do

begin

inc(o);

if o>1000000 then break;

u:=y[i];

ww:=fmin(w[u],d1[v]);

if ww<d1[u] then d1[u]:=ww;

if not flag[u] then

begin

t:=(t mod 100000)+1;

q[t]:=u;

flag[u]:=true;

end;

end;

if o>1000000 then break;

end;

end;

procedure spfa2;

var i,h,t,v,u,o,ww:longint;

begin

for i:=1 to e do

swap(x[i],y[i]);

qs(1,e);

fillchar(f,sizeof(f),0);

for i:=1 to e do

if f[x[i]]=0 then f[x[i]]:=i;

f[n+1]:=e+1;

for i:=n downto 1 do

if f[i]=0 then f[i]:=f[i+1];

fillchar(d2,sizeof(d2),0);

fillchar(flag,sizeof(flag),false);

fillchar(q,sizeof(q),0);

h:=0;t:=1;q[t]:=n;flag[n]:=true;d2[n]:=w[n];o:=0;

while h<>t do

begin

h:=(h mod 100000)+1;

v:=q[h];

flag[v]:=false;

if f[v]<>0 then

for i:=f[v] to f[v+1]-1 do

begin

inc(o);

if o>1000000 then break;

u:=y[i];

ww:=fmax(w[u],d2[v]);

if ww>d2[u] then d2[u]:=ww;

if not flag[u] then

begin

t:=(t mod 100000)+1;

q[t]:=u;

flag[u]:=true;

end;

end;

if o>1000000 then break;

end;

end;

procedure print;

var i,max:longint;

begin

max:=0;

for i:=1 to n do

if (d1[i]<>200)and(d2[i]<>0)and(d2[i]-d1[i]>max) then max:=d2[i]-d1[i];

writeln(max);

end;

begin

init;

spfa1;

spfa2;

print;

end.

#1 77@2012-07-31 08:04:00
回复 删除
弱弱的问一下 怎么看你做的是哪题?
#2 77@2012-07-31 08:04:00
回复 删除
弱弱的问一下 怎么看你做的是哪题?

弱弱的问一下 怎么看你做的是哪题?

查看更多回复
提交回复