讨论 / 高分求分析
q1041554836 2013-08-31 04:49:00
点我顶贴 收藏 删除
var d,y1,y2,v:array[0..200000]of longint;z:array[1..2]of longint;

f,x,xx,g,yy,ne,we:array[1..2,0..500000]of longint;

n,m,i,j,k,a,b,c,st,en,max:longint;

begin

assign(input,'trade.in');

assign(output,'trade.out');

reset(input);

rewrite(output);

readln(n,m);

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

for i:=1 to m do

begin

inc(k);

readln(z[1],z[2],a);

for j:=1 to a do

begin

b:=z[j];c:=z[3-j];

if j=2 then inc(k);

if yy[1,b]=0 then begin yy[1,b]:=1;x[1,b]:=k;g[1,b]:=k;end

else begin ne[1,g[1,b]]:=k;g[1,b]:=k;end;

inc(xx[1,b]);

we[1,k]:=c;

if yy[2,c]=0 then begin yy[2,c]:=1;x[2,c]:=k;g[2,c]:=k;end

else begin ne[2,g[2,c]]:=k;g[2,c]:=k;end;

we[2,k]:=b;

inc(xx[2,c]);

end;

end;

for i:=1 to n do

begin

f[1,i]:=v[i];

f[2,i]:=v[i];

end;

for i:=1 to 2 do

begin

fillchar(y1,sizeof(y1),0);

fillchar(y2,sizeof(y2),0);

fillchar(d,sizeof(d),0);

st:=0;en:=1;

if i=1 then begin d[1]:=1;y2[1]:=1;f[i,1]:=10000;f[i,n]:=10000;end

else begin d[1]:=n;y2[n]:=1;f[i,n]:=0;f[i,1]:=0;end;

while st<>en do

begin

st:=(st mod n)+1;

a:=x[i,d[st]];

b:=we[i,a];

if i=1 then

begin

for j:=1 to xx[i,st] do

begin

if f[i,b]>f[i,d[st]] then

begin

f[i,b]:=f[i,d[st]];

if y1[b]=0 then begin en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;end;

end;

if (f[i,b]<=f[i,d[st]])and(y2[b]=0)then

begin

en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;

end;

a:=ne[i,a];

b:=we[i,a];

end;

end;

if i=2 then

begin

for j:=1 to xx[i,st] do

begin

if f[i,b]<f[i,d[st]] then

begin

f[i,b]:=f[i,d[st]];

if y1[b]=0 then begin en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;end;

end;

if (f[i,b]>=f[i,d[st]])and(y2[b]=0)then

begin

en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;

end;

a:=ne[i,a];

b:=we[i,a];

end;

end;

y1[st]:=0;

end;

end;

max:=0;

for i:=2 to n-1 do

if max<f[2,i]-f[1,i] then max:=f[2,i]-f[1,i];

writeln(max);

readln;

close(input);

close(output);

end.

#1 初夏、樱花落@2013-08-24 05:00:00
回复 删除
[话说……]

[color=red]

话说……悬赏什么滴太不真实了昂~你记个【注释:这个】程序似哪道题目呐~~看下题目,谢谢昂~

#2 107229HR@2013-08-24 05:17:00
回复 删除
回复 沙发初夏、樱花落 的帖子

http://www.rqnoj.cn/Problem_520.html

#3 王昱炜3号@2013-08-24 06:57:00
回复 删除
重金之下,必有勇夫

rt

#4 absi2011@2013-08-24 17:39:00
回复 删除
回复 地毯王昱炜3号 的帖子

一般重赏下会有管理员来,然后让LZ自己思考不然把分就乱给

我不是那样的人~

http://www.rqnoj.cn/Discuss_Show.asp?DID=8986

某人的帖子

#5 lishuhanji@2013-08-30 05:33:00
回复 删除
回复 地毯王昱炜3号 的帖子

人品+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

#6 王帅炜@2013-08-31 04:49:00
回复 删除
回复 地板absi2011 的帖子

那太好了,快把分乱给我把

查看更多回复
提交回复