讨论 / noip2009第三题
wjzzm 2010-11-08 00:00:00
点我顶贴 收藏 删除
本人比较菜,不会用链表,用二维数组存的,

program s1;

var a:array[0..1000,0..1000]of longint;

zheng,fan,v:array[1..1000]of longint;

i,j,k,l,n,m,o,p:longint;

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

begin

if a< b then exit(a)

else exit(b);

end;

procedure spfa;

var t:array[1..1000000]of longint;

b:array[1..1000]of boolean;

i,j,k,tou,wei:longint;

begin

fillchar(b,sizeof(b),true);

b[1]:=false; t[1]:=1;

zheng:=v;

tou:=1;wei:=1;

while tou<=wei do

begin

if tou>100000 then break;

k:=t[tou];

for i:=1 to a[k,0] do

begin

if zheng[a[k,i]]>min(v[a[k,i]],zheng[k]) then zheng[a[k,i]]:=min(zheng[k],v[a[k,i]]);

if b[a[k,i]] then

begin

inc(wei);

t[wei]:=a[k,i];

b[a[k,i]]:=false;

end;

end;

b[t[tou]]:=true;

inc(tou);

end;

end;

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

begin

if a>b then exit(a)

else exit(b);

end;

procedure spfa2;

var t:array[1..10000]of longint;

b:array[1..1000]of boolean;

i,j,k,tou,wei:longint;

begin

fillchar(b,sizeof(b),true);

b[n]:=false; t[1]:=n;

fan:=v;

tou:=1;wei:=1;

while tou<=wei do

begin

k:=t[tou];

if tou>100000 then break;

for i:=1 to a[k,0] do

begin

if fan[a[k,i]]<max(v[a[k,i]],fan[k]) then fan[a[k,i]]:=max(fan[k],v[a[k,i]]);;

if b[a[k,i]] then

begin

inc(wei);

t[wei]:=a[k,i];

b[a[k,i]]:=false;

end;

end;

b[t[tou]]:=true;

inc(tou);

end;

end;

procedure int;

var i,j,k,l:longint;

begin

assign(input,'1.in');

reset(input);

readln(n,m);

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

for i:=1 to m do

begin

readln(j,k,l);

if l=1 then

begin

inc(a[j,0]);

a[j,a[j,0]]:=k;

end

else

begin

inc(a[j,0]);

a[j,a[j,0]]:=k;

inc(a[k,0]);

a[k,a[k,0]]:=j;

end;

end;

end;

begin

int;

spfa;

spfa2;

k:=0;

for i:=1 to n do k:=max(k,fan[i]-zheng[i]);

if k>0 then write(k)

else write(0);

end.

牛门看看那里错了。。。

#1 luoxiangyu@2010-08-21 02:30:00
回复 删除
不需要用链表吧,反正我是用的前向星
#2 407137009@2010-11-07 22:28:00
回复 删除
用前向星的话,m<=500000,排序都要很费时间的吧
#3 407137009@2010-11-08 00:00:00
回复 删除
一遍SPFA+前向星优化(速度很勉强)

状态: Accepted

测评机: Xeond[6]

得分: 100分

提交日期: 2010-11-8 15:16:00

有效耗时: 4047毫秒

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

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

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

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

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

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

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

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

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

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

type

node=record

sta,en:longint;

end;

var

map:array[1..1000000] of node;

k,cost,max,min:array[1..100000] of longint;

mark:array[1..100000] of boolean;

f:array[1..1000000] of longint;

tol,x,y,z,now,head,tail,n,i,m:longint;

procedure qsort(g,h:longint);

var

head,tail:longint;

mid:node;

begin

head:=g;tail:=h;mid:=map[g];

while g<h do

begin

while (g<h)and(map[h].sta>=mid.sta) do h:=h-1;

map[g]:=map[h];

while (g<h)and(map[g].sta<=mid.sta) do g:=g+1;

map[h]:=map[g];

end;

map[g]:=mid;

if head<g-1 then qsort(head,g-1);

if tail>g+1 then qsort(g+1,tail);

end;

procedure init;

begin

readln(n,m);

for i:=1 to n do

begin

read(cost[i]);

min[i]:=cost[i];

end;

readln;

for i:=1 to m do

begin

readln(x,y,z);

inc(tol);

map[tol].sta:=x;

map[tol].en:=y;

if z=2 then

begin

inc(tol);

map[tol].sta:=y;

map[tol].en:=x;

end;

end;

end;

procedure fill;

begin

fillchar(max,sizeof(max),$ff);

max[1]:=0;

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

head:=1;tail:=1;

f[1]:=1;

fillchar(mark,sizeof(mark),true);

mark[1]:=false;

qsort(1,tol);

for i:=1 to tol do

if k[map[i].sta]=0 then k[map[i].sta]:=i;

k[n+1]:=tol+1;

for i:=n downto 1 do

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

end;

begin

init;

fill;

while head<=tail do

begin

now:=f[head];

for i:=k[now] to k[now+1]-1 do

if (max[now]>max[map[i].en])or(min[now]<min[map[i].en])then

begin

if min[now]<min[map[i].en] then min[map[i].en]:=min[now];

if max[now]>max[map[i].en] then max[map[i].en]:=max[now];

if cost[map[i].en]-min[map[i].en]>max[map[i].en] then

max[map[i].en]:=cost[map[i].en]-min[map[i].en];

if mark[map[i].en] then

begin

tail:=tail+1;

f[tail]:=map[i].en;

mark[map[i].en]:=false;

end;

end;

head:=head+1;

mark[now]:=true;

end;

writeln(max[n]);

end.

查看更多回复
提交回复