【CF666B】World Tour（贪心，最短路）
2024-10-21 19:43:00
题意：给你一张有向图，叫你给出四个点的序列a,b,c,d，使得这四个点依次间的最短路之和最大。(4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000)
思路：O(n4)可用来对拍
我们需要O（n2）级别的算法
若枚举c,d，预处理出x到b比较远的3个x，d到y比较远的3个y，时间复杂度O(9n2)
为什么是3个而不是2个？
abc已枚举，若d的备选是ab就要GG，所以应该多一个备用，也就是三个点
var c,d:array[..,..,..]of longint;
head,vet,next,b,flag,q,x,y:array[..]of longint;
dis:array[..]of longint;
save:array[..,..]of longint;
n,m,tot,i,s1,s2,s3,s4,a1,b1,c1,d1,ans,j,k,s,p1,q1:longint; procedure add(a,b:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
head[a]:=tot;
end; procedure bfs(x:longint);
var t,w,e,u,v:longint;
begin
fillchar(b,sizeof(b),);
fillchar(dis,sizeof(dis),);
t:=; w:=; q[]:=x; b[x]:=; dis[x]:=;
while t<=w do
begin
u:=q[t]; inc(t);
e:=head[u];
while e<> do
begin
v:=vet[e];
if b[v]= then
begin
dis[v]:=dis[u]+;
b[v]:=;
inc(w); q[w]:=v;
end;
e:=next[e];
end;
end;
end; begin
//assign(input,'1.in'); reset(input);
//assign(output,'1.out'); rewrite(output);
readln(n,m);
for i:= to m do
begin
readln(x[i],y[i]);
add(x[i],y[i]);
end; for i:= to n do
begin
bfs(i);
k:=; s:=;
fillchar(flag,sizeof(flag),);
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; c[i,,]:=k; c[i,,]:=s;
k:=; s:=;
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; c[i,,]:=k; c[i,,]:=s;
k:=; s:=;
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; c[i,,]:=k; c[i,,]:=s; // x---->c[i] ,,
for j:= to n do save[i,j]:=dis[j];
end; fillchar(head,sizeof(head),);
tot:=;
for i:= to m do add(y[i],x[i]); for i:= to n do
begin
bfs(i);
k:=; s:=;
fillchar(flag,sizeof(flag),);
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; d[i,,]:=k; d[i,,]:=s;
k:=; s:=;
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; d[i,,]:=k; d[i,,]:=s;
k:=; s:=;
for j:= to n do
if (flag[j]=)and(dis[j]>s) then
begin
k:=j; s:=dis[j];
end;
flag[k]:=; d[i,,]:=k; d[i,,]:=s; // d[i] ---->i
end; s1:=; s2:=; s3:=; s4:=; ans:=-maxlongint;
for b1:= to n do
for c1:= to n do
if save[b1,c1]> then
for p1:= to do
for q1:= to do
begin
d1:=c[c1,p1,];
a1:=d[b1,q1,]; //a1-->b1-->c1-->d1
if (a1<>b1)and(a1<>c1)and(a1<>d1)and(b1<>c1)and(b1<>d1)and(c1<>d1) then
if d[b1,q1,]+c[c1,p1,]+save[b1,c1]>ans then
begin
s1:=a1; s2:=b1; s3:=c1; s4:=d1;
ans:=d[b1,q1,]+c[c1,p1,]+save[b1,c1];
end;
end;
writeln(s1,' ',s2,' ',s3,' ',s4); //close(input);
//close(output);
end.
最新文章
- Java 中正确获取中文字符串长度
- Linux平台Cpu使用率的计算
- Ubuntu环境下手动配置tomcat
- SQL 2008 R2 启动失败 提示 请求失败或服务未及时响应
- HashMap多线程死循环问题
- [zz] makefile中=和:=的区别
- Linux下修改字符集，转自
- MVC Razor标签
- NOI2004 郁闷的出纳员 Splay
- Java基础笔记12
- 【搬运】Tea算法Java实现工具类
- Java面试题积累
- 6.0、Android Studio性能优化工具
- UNIX网络编程——epoll的 et，lt关注点
- vue-router组件重用 路由切换时的问题
- openstack搭建之-基础服务配置（7）
- IBM MQ 使用指南
- Groovy 反射字符串常量方法
- PXC 57 二进制安装
- java中Future与FutureTask使用与分析