bzoj2535 2109
2024-09-25 15:49:59
做过4010这题其实就水了
把图反向之后直接拓扑排序做即可，我们可以用链表来优化
每个航班的最小起飞序号就相当于在反向图中不用这个点最迟到哪
type node=record
po,next:longint;
end; var e:array[..] of node;
ans,p,h,suc,du,d,a:array[..] of longint;
i,x,y,n,m:longint; procedure add(x,y:longint);
begin
e[i].po:=y;
e[i].next:=p[x];
p[x]:=i;
end; procedure merge(x,y:longint);
begin
if h[x]= then h[x]:=h[y]
else begin
x:=h[x];
while suc[x]<> do x:=suc[x];
suc[x]:=h[y];
end;
end; function min(wh:longint):longint;
var i,x,y,t,b:longint;
begin
for i:= to n do
begin
du[i]:=d[i];
h[i]:=;
end;
for i:= to n do
if (i<>wh) and (d[i]=) then
begin
suc[i]:=h[a[i]];
h[a[i]]:=i;
end;
t:=n;
while t> do
begin
x:=h[t];
if x= then exit(t);
h[t]:=suc[h[t]];
i:=p[x];
while i<> do
begin
y:=e[i].po;
dec(du[y]);
if (y<>wh) and (du[y]=) then
begin
if a[y]<t then b:=a[y]
else b:=t;
suc[y]:=h[b];
h[b]:=y;
end;
i:=e[i].next;
end;
merge(t-,t);
dec(t);
end;
exit();
end; procedure work1;
var i,x,y,t,b:longint;
begin
for i:= to n do
begin
du[i]:=d[i];
h[i]:=;
end;
for i:= to n do
if d[i]= then
begin
suc[i]:=h[a[i]];
h[a[i]]:=i;
end;
t:=n;
while t> do
begin
x:=h[t];
ans[t]:=x;
h[t]:=suc[h[t]];
i:=p[x];
while i<> do
begin
y:=e[i].po;
dec(du[y]);
if du[y]= then
begin
if a[y]<t then b:=a[y]
else b:=t;
suc[y]:=h[b];
h[b]:=y;
end;
i:=e[i].next;
end;
merge(t-,t);
dec(t);
end;
for i:= to n- do
write(ans[i],' ');
writeln(ans[n]);
end; procedure work2;
var i:longint;
begin
for i:= to n- do
write(min(i),' ');
writeln(min(n));
end; begin
readln(n,m);
for i:= to n do
begin
read(a[i]);
if a[i]>n then a[i]:=n;
end;
for i:= to m do
begin
readln(x,y);
add(y,x);
inc(d[x]);
end;
work1;
work2;
end.
最新文章
- sql monitor生成不了报告& FFS hint不生效两个问题思考
- Oracle not in子连接查询不到值的问题（not in 不能查询null数据）
- ipcs命令
- 关于windows程序的学习及思考系列之一
- VC ClistCtrl不同行背景色
- Spring 4 Ehcache Configuration Example with @Cacheable Annotation
- linux下定时发送邮件
- jsp中Java代码中怎么获取jsp页面元素
- Hibernate 配置详解(12) 其实我也不想用这么土的名字
- mysql 查看数据库中所有表的记录数
- Composer 是什么
- VBA小技巧
- DAY18、常用模块
- 利用efi功能更改bios主板被隐藏的设置（如超频）
- DP思想笔记
- Vue - v-for 的延伸用法
- left join on 和where中条件的放置位置
- CSS3--难以想象的滤镜效果
- Zookeeper与Paxos
- linux系统时间不同步解决办法（同步本地时间）