noip2009 pascal 最优贸易 求宽搜做法 不要用spfa（看不懂！）
有一个N 个结点的有向图，从1 号结点出发，到达N 号结点，在其中的
一个结点买入，另一个结点卖出，使所得的差价最大。求最大的差价。
广度优先算法。从1 号结点开始搜，每次把可以更新的结点入队，直到
找不到可以更新的结点为止。在搜索的过程中，需要对每个结点保存两个值：一个是
从起点到这个点的最低买入价格minp[i]，另一个是从起点到这个点的最大利润ma x[i]。
在更新值的时候，要保证是先买入再卖出。
更新方法如下：
假设结点u 与结点v 有一条有向边连接，目前访问结点v，则：
if minp[p^.data]>minp[u] then minp[p^.data]:= minp[u]; {更新p^.data 的最低买入价格}
if ma x[u]>ma x[p^.data] then ma x[p^.data]:= max[u]; {更新p^.data 的最大利润}
if price[p^.data]-minp[p^.data]>ma x[p^.data] then {更新p^.data 的最大利润}
ma x[p^.data]:=price[p^.data]-minp[p^.data];
【参考程序】
const ma xn = 100001; ma xm = 500001;
type pointer = ^rec;
rec=record
data: longint ;
next:pointer;
end ;
var
f:array [1..ma xn] of pointer;
q:array [1..2*ma xn] of longint;
mark:a rray [1..ma xn] of boolea n;
price,minp, ma x : array [1..ma xn] of longint;
n,m,i,min1,ma x1: longint;
procedure init;
var i , x , y , z : longint;
p:pointer;
begin
ma x1:=0; min1:= ma xlongint;
for i:=1 to ma xn do
begin new(f[i]);f[i]:= nil; end;
readln(n,m);
for i := 1 to n do
read(price[i]);
readln;
for i := 1 to m do
begin
readln(x,y,z);
第6页，共10页
new(p);
p^.data:= y;
p^.next:= f[x];
f[x]:=p;
if z = 2 then
begin
new(p); p^.data:= x; p^.next:= f[y]; f[y]:=p;
end;
end;
end;
procedure spfa;
var head,ta il,u: longint ;
p:pointer;
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to ma xn do
ma x[i]:=-1;
head := 0 ; tail := 1 ;
q[1] :=1 ;
mark[1] := true;
for i:=1 to n do
minp[i] :=price[i] ; {初始化最低买入价格}
ma x[1]:=0; {顶点1 的最大利润初值为0}
repeat
inc (head) ; if (head > ma xn) then head := 1 ;
u := q[head] ;
mark[u] := false ;
p := f[u];
while (p nil) do
begin
if (minp[p^.data]>minp[u]) or (ma x[u]>ma x[p^.data]) then
begin
if minp[p^.data]>minp[u] then minp[p^.data]:= minp[u]; {更新p^.data
的最低买入价格}
if ma x[u]>ma x[p^.data] then ma x[p^.data]:= max[u]; {更新p^.data
的最大利润}
if price[p^.data]-minp[p^.data]>ma x[p^.data] then
ma x[p^.data]:=price[p^.data]-minp[p^.data];
if not mark[p^.data] then
begin
inc(tail);
if (tail > ma xn) then tail := 1 ;
q[tail]:=p^.data;
第7页，共10页
mark[p^.data]:= true;
end;
end;
p:=p^.next;
end;
until (head = tail) ;
if ma x[n]>-1 then writeln(max[n]);
end ;
begin
assign(input,'trade.in'); reset(input);
assign(output,'trade.out'); rewrite(output);
init;
spfa;
close(input); close(output);
end.
program cdsfc;
var
i,n,m,ans,xx,yy,mmax,mmin:longint;
x,y,z:array[0..500000] of longint;
a,f,max,min,g:array[0..100000] of longint;
v:array[0..100000] of boolean;
function find(t:longint):longint;
begin
if f[t]t then find:=find(f[t])
else find:=t;
f[t]:=find;
end;
procedure init;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
read(x[i],y[i],z[i]);
if z[i]=2 then f[find(x[i])]:=find(y[i]);
end;
for i:=1 to n do
begin
max[i]:=a[i];
min[i]:=a[i];
end;
for i:=1 to m do
begin
xx:=find(x[i]);
yy:=find(y[i]);
if a[x[i]]>max[xx] then max[xx]:=a[x[i]];
if a[x[i]]<min[xx] then min[xx]:=a[x[i]];
if a[y[i]]>max[yy] then max[yy]:=a[y[i]];
if a[y[i]]<min[yy] then min[yy]:=a[y[i]];
if z[i]=2 then
begin
if a[x[i]]>max[yy] then max[yy]:=a[x[i]];
if a[x[i]]<min[yy] then min[yy]:=a[x[i]];
if a[y[i]]>max[xx] then max[xx]:=a[y[i]];
if a[y[i]]<min[xx] then min[xx]:=a[y[i]];
end;
x[i]:=xx;
y[i]:=yy;
end;
end;
procedure sort(l,r:longint);
var
i,j,ix,iy:longint;
begin
i:=l;
j:=r;
ix:=x[(l+r)shr 1];
repeat
while x[i]<ix do inc(i);
while ix<x[j] do dec(j);
if i<=j then
begin
iy:=x[i];
x[i]:=x[j];
x[j]:=iy;
iy:=y[i];
y[i]:=y[j];
y[j]:=iy;
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure dfs1(k:longint);
var
j:longint;
begin
min[k]:=mmin;
if k=n then exit;
if v[k] then exit;
v[k]:=true;
for j:=g[k-1] to g[k]-1 do
begin
if mmin>min[y[j]] then mmin:=min[y[j]];
dfs1(y[j]);
mmin:=min[k];
end;
end;
procedure dealmin;
begin
sort(1,m);
for i:=1 to m+1 do
if x[i]x[i-1] then g[x[i-1]]:=i;
for i:=1 to n do if g[i]=0 then g[i]:=g[i-1];
g[0]:=1;
mmin:=min[1];
dfs1(1);
end;
procedure qsort(l,r:longint);
var
i,j,ix,iy:longint;
begin
i:=l;
j:=r;
ix:=y[(l+r)shr 1];
repeat
while y[i]<ix do inc(i);
while ix<y[j] do dec(j);
if i<=j then
begin
iy:=x[i];
x[i]:=x[j];
x[j]:=iy;
iy:=y[i];
y[i]:=y[j];
y[j]:=iy;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure dfs2(k:longint);
var
j:longint;
begin
max[k]:=mmax;
if (max[k]-min[k]>ans) then ans:=max[k]-min[k];
if k=1 then exit;
if v[k] then exit;
v[k]:=true;
for j:=g[k-1] to g[k]-1 do
begin
if mmax<max[x[j]] then mmax:=max[x[j]];
dfs2(x[j]);
mmax:=max[k];
end;
end;
procedure dealmax;
begin
qsort(1,m);
fillchar(g,sizeof(g),0);
fillchar(v,sizeof(v),false);
for i:=1 to m+1 do
if y[i]y[i-1] then g[y[i-1]]:=i;
for i:=1 to n do if g[i]=0 then g[i]:=g[i-1];
g[0]:=1;
mmax:=max[n];
dfs2(n);
end;
begin
init;
dealmin;
dealmax;
writeln(ans);
end.
在没你提醒之前 我只会用spfa做
但经你提醒之后 我用BFS写出来了 哈哈
两边BFS速度还凑合 没优化 看看吧
还有楼上 前向星存储是什么啊？ 说明一下呗 我因为是自学的所以知道的术语少，本人只会 写这个insert 也不知道是什么方式
这个题真是坑人啊 没想到起点和终点不能买东西竟然！！
害我wa了好几次
修正 把路径长设置为1
const maxn=10000001;
var nnum,bback,ffront,num,back,front:array[1..maxn]of longint;
a:array[1..maxn]of longint;
dist1,dist2:array[1..maxn]of longint;
minn:array[1..maxn]of longint;
maxx:array[1..maxn]of longint;
i,j,m,n,l,q,w,min,max,e,f,now,b,r,t,y,x,z,u:longint;
q1,q2:array[1..maxn]of longint;
procedure insert(x,y:longint);
begin
inc(t);
bback[t]:=x;
ffront[t]:=nnum[y];
nnum[y]:=t;
back[t]:=y;
front[t]:=num[x];
num[x]:=t;
end;
begin
readln(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do
begin
readln(x,y,z);
insert(x,y);
if z=2 then insert(y,x);
end;
q1[1]:=1;
l:=0; r:=1;
fillword(dist1,sizeof(dist1)>>2,1000);
fillword(dist2,sizeof(dist2)>>2,1000);
fillword(minn,sizeof(minn)>>2,1000);
fillword(maxx,sizeof(maxx)>>2,0);
dist1[1]:=0;
while l<r do
begin
inc(l);
f:=q1[l];
now:=num[f];
while now<>0 do
begin
b:=back[now];
if (dist1[b]>dist1[f]+1)or(maxx[b]<maxx[f]) then
begin
dist1[b]:=dist1[f]+1;
inc(r);
q1[r]:=b;
if a[b]>maxx[f] then maxx[b]:=a[b] else if maxx[f]>maxx[b] then maxx[b]:=maxx[f];
end;
now:=front[now];
end;
end;
q2[1]:=n;
l:=0; r:=1;
dist2[n]:=0;
min:=maxlongint;
while l<r do
begin
inc(l);
f:=q2[l];
now:=nnum[f];
while now<>0 do
begin
b:=bback[now];
if (dist2[b]>dist2[f]+1)or(minn[b]>minn[f]) then
begin
dist2[b]:=dist2[f]+1;
inc(r);
q2[r]:=b;
if a[b]<minn[f] then minn[b]:=a[b]
else if minn[b]>minn[f] then minn[b]:=minn[f];
end;
now:=ffront[now];
end;
end;
for i:=2 to n-1 do
if maxx[i]-minn[i]>e then e:=maxx[i]-minn[i];
writeln(e);
end.
状态: Accepted
测评机： Xeond[6]
得分： 100分
提交日期： 2010-11-10 19:02:00
有效耗时： 3891毫秒
测试结果1: 通过本测试点|有效耗时188ms
测试结果2: 通过本测试点|有效耗时62ms
测试结果3: 通过本测试点|有效耗时188ms
测试结果4: 通过本测试点|有效耗时609ms
测试结果5: 通过本测试点|有效耗时687ms
测试结果6: 通过本测试点|有效耗时157ms
测试结果7: 通过本测试点|有效耗时203ms
测试结果8: 通过本测试点|有效耗时390ms
测试结果9: 通过本测试点|有效耗时704ms
测试结果10: 通过本测试点|有效耗时703ms
其实spfa就是用宽搜的框架，和宽搜差不多，由于数据比较大，要用前向星记录。
附上鄙人的程序：
program T_1122;
type rt=record a,b:longint; end;
var e:array[1..1000010]of rt;
d:array[1..2,1..100010]of longint;
q,f,a:array[0..100010]of longint;
v:array[1..100010]of boolean;
x,y,z,i,j,n,m,h,t,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure qsort(s,t:longint);
var i,j,x:longint;
p:rt;
begin
i:=s;
j:=t;
x:=e[(i+j)div 2].a;
repeat
while x>e[i].a do inc(i);
while x<e[j].a do dec(j);
if i<=j then
begin
p:=e[i];
e[i]:=e[j];
e[j]:=p;
dec(j);inc(i);
end;
until i>j;
if i<t then qsort(i,t);
if s<j then qsort(s,j);
end;
begin
read(n,m);
for i:=1 to n do
read(a[i]);
t:=0;
for i:=1 to m do
begin
read(x,y,z);
inc(t);
e[t].a:=x;
e[t].b:=y;
if z=2 then
begin
inc(t);
e[t].a:=y;
e[t].b:=x;
end;
end;
m:=t;
qsort(1,m);
fillchar(f,sizeof(f),0);
for i:=1 to m do
if f[e[i].a]=0 then f[e[i].a]:=i;
f[n+1]:=m+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
fillchar(v,sizeof(v),0);
fillchar(d[1],sizeof(d[1]),100);
q[1]:=1;
h:=0;
t:=1;
v[1]:=true;
d[1,1]:=a[1];
while h<>t do
begin
h:=(h+1) mod n;
x:=q[h];
for i:=f[x] to f[x+1]-1 do
if d[1,e[i].b]>min(d[1,x],a[e[i].b]) then
begin
d[1,e[i].b]:=min(d[1,x],a[e[i].b]);
if not(v[e[i].b]) then
begin
t:=(t+1) mod n;
q[t]:=e[i].b;
v[q[t]]:=true;
end;
end;
v[x]:=false;
end;
for i:=1 to m do
begin
x:=e[i].a;
e[i].a:=e[i].b;
e[i].b:=x;
end;
qsort(1,m);
fillchar(f,sizeof(f),0);
for i:=1 to m do
if f[e[i].a]=0 then f[e[i].a]:=i;
f[n+1]:=m+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
fillchar(v,sizeof(v),0);
fillchar(d[2],sizeof(d[2]),0);
fillchar(q,sizeof(q),0);
d[2,n]:=a[n];
q[1]:=n;
h:=0;
t:=1;
v[n]:=true;
while h<>t do
begin
h:=(h+1) mod n;
x:=q[h];
for i:=f[x] to f[x+1]-1 do
if d[2,e[i].b]<max(d[2,x],a[e[i].b]) then
begin
d[2,e[i].b]:=max(d[2,x],a[e[i].b]);
if not(v[e[i].b]) then
begin
t:=(t+1) mod n;
q[t]:=e[i].b;
v[q[t]]:=true;
end;
end;
v[x]:=false;
end;
ans:=0;
for i:=1 to n do
if ans<d[2,i]-d[1,i] then ans:=d[2,i]-d[1,i];
writeln(ans);
end.
SPFA就是边宽搜边松弛嘛！（SPFA算法拓展性很强的，很好！）
你在百度上搜“最优贸易 题解”，第一个，CSDN博客写的题解很好，就看中间那一段话，你就明白了。
SPFA，我反正没用过前向星，我一般用 指针链表+循环队列
这个题可以先用scc缩点，然后从两侧进行dp
满胡和乐： NOIP2009初赛普及组(C语言、PASCAL语言)参考答案与评分标准 一、单项选择题:(每题1.5分) 1. D 2. B 3. A 4. A 5. B6. D 7. C 8. B 9. C 10. D11. C 12. C 13. B 14. D 15. D 16. B 17. D 18. A 19. C 20. B 二、问题求解:(共2题,每空5分...
隆昌县15641906675： noip2009普及组初赛讲解 答案 - ？
满胡和乐： NOIP2009初赛普及组(C语言、PASCAL语言)参考答案与评分标准 一、单项选择题:(每题1.5分)1. D 2. B 3. A 4. A 5. B6. D 7. C 8. B 9. C 10. D11. C 12. C 13. B 14. D 15. D16. B 17. D 18. A 19. C 20. B二、问题求解:(共2题,每...
隆昌县15641906675： NOIP2009普及组初赛三题4题 - ？
满胡和乐： 原题目确实有错误,标准答案为NPOI 附:关于NOIP2009初赛普及组Pascal语言一道题目的问题与阅卷处理意见 经查,NOIP2009 初赛普及组(Pascal版本)第四大题(阅读程序写结果)第4小题题 目中存在一处数据输入格式的错误:该题提供...
隆昌县15641906675： noip中推荐使用的pascal的版本是什么？
满胡和乐： http://www.noi.cn/noi2009-noip2009去官方网站看
隆昌县15641906675： 求pascal noip2009潜伏者的解题思路? - ？
满胡和乐： var s1,s2,s3:string; a,b:array['A'..'Z']of char; i:longint; c:char; begin readln(s1); readln(s2); readln(s3);//s1为一条加密信息,s2为原信息.通过他们找到密码与原码之间的对应关系. //一个加密字母对应一个原码字母(用a表示);一个原码字母对应...
隆昌县15641906675： [NOIP]C++该不该转Pascal? - ？
满胡和乐： 如果你的目标是获得NOIP一等奖的话,我建议你转.因为NOIP里面pascal的语言有着更多的优势,写起来也更容易,收到的束缚也会少很多.但是如果你是想学了有用的话,还是建议学C++,因为等你上了大学会发现PASCAL基本没什么用处,并且黑屏的操作方式早已经被淘汰.而C++却是一个热门的语言.
隆昌县15641906675： 2009NOIP LINUX 复测 PASCAL - ？
满胡和乐： 不会的. 全局变量不赋值没事,如果是过程函数中的局部变量不赋值,不论是从 Windows 下还是 Linux 下,都会出问题的. 补充:在全局变量里,如果不初始化的话初始值就是0. 所以不会出现你说的这种情况.
隆昌县15641906675： 第十七届全国青少年信息学奥林匹克联赛初赛答案？
满胡和乐： NOIP2009初赛提高组答案(Pascal版) 一、单项选择题:(每题1.5分)1.C2.A3.D4.B5.D6.B7.B8.A9.A10.C二、不定项选择题(共10题,每题1.5分,共计15分.每题正确答案的个数大于或等于1.多选或少选均不得分).1.AB2.BD 3.BC4.C ...
隆昌县15641906675： noip 2009 普及组初赛答案 - ？
满胡和乐： 一、单项选择题:(每题1.5分)1. D 2. B 3. A 4. A 5. B6. D 7. C 8. B 9. C 10. D11. C 12. C 13. B 14. D 15. D16. B 17. D 18. A 19. C 20. B 二、问题求解:(共2题,每空5分,共计10分)1.702.5 三、阅读程序写结果(共4题,每题8分,共计32...
隆昌县15641906675： 有谁知道第十五届青少年信息学竞赛初赛试题答案啊? - ？
满胡和乐： NOIP2009年普及组(Pascal语言)参考答案与评分标准一、单项选择题:(每题1.5分) 1. D 2. B 3. A 4. A 5. B 6. D 7. C 8. B 9. C 10. D 11. C 12. C 13. B 14. D 15. D 16. B 17. D 18. A 19. C 20. B 二、问题求解:(共2题,每空5分,共计10分...
