P8817 [CSP-S 2022] 假期计划

[CSP-S 2022] 假期计划

我第一眼看的时候怎么搞都会多一个 \(O(\log n)\)，还在想是不是有什么高深做法……

然后想到边权为 \(1\) 的时候好像根本不需要用 Dijkstra，直接 BFS 不就得了……

那么我们预处理出每个点之间的距离实际上是 \(O(n(n+m))\) 的。

剩下的事情就很简单了，我们针对每个点 \(x\)，找到点权最大的三个点，这三个点满足条件：既可以到达 \(x\) 又可以到达源点。

然后我们枚举路程中间的两个点 \(B,C\)，枚举比较一下就结束了。这一块的复杂度是 \(O(n^2)\) 的。

最后的时间复杂度就是 \(O(n(n+m))\) 的。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll inf=1e9,N=2.5e3,M=1e4;

ll n,m,k,tot,ans,u,v,h;
ll f[N+5][N+5],ver[M*2+5],nxt[M*2+5],head[N+5],a[N+5],ma[4][N+5];
bool vis[N+5];
queue<ll> q;

inline void Add(ll u,ll v) {ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

int main() {
  
  n=read();m=read();k=read();
  for(ll i=2;i<=n;i++) {a[i]=read();}
  tot=1;
  for(ll i=1;i<=m;i++) {u=read();v=read();Add(u,v);Add(v,u);}
  
  for(ll j=1;j<=n;j++) {
    for(ll i=1;i<=n;i++) f[j][i]=inf;
    for(ll i=1;i<=n;i++) vis[i]=0;
    while(!q.empty()) q.pop();q.push(j);f[j][j]=0;vis[j]=1;
    while(!q.empty()) {
      h=q.front();q.pop();
      if(f[1][h]<=k+1&&f[j][h]<=k+1&&a[h]>0&&h!=j&&h!=1) {
        if(a[h]>=a[ma[1][j]]) {ma[3][j]=ma[2][j];ma[2][j]=ma[1][j];ma[1][j]=h;}
        else if(a[h]>=a[ma[2][j]]) {ma[3][j]=ma[2][j];ma[2][j]=h;}
        else if(a[h]>=a[ma[3][j]]) {ma[3][j]=h;}
      }
      if(f[j][h]>=k+1) continue;
      for(ll i=head[h];i;i=nxt[i]) {
        if(vis[ver[i]]) continue;vis[ver[i]]=1;
        f[j][ver[i]]=f[j][h]+1;q.push(ver[i]);
      }
    }
  }
  
  for(ll i=2;i<=n;i++) {
    for(ll j=2;j<=n;j++) {
      if(i==j) continue;
      if(f[i][j]<=k+1) {
        ll tmp=a[i]+a[j];ll flg=0;
        for(ll p=1;p<=3;p++) {
          if(ma[p][i]<=1) continue;
          if(ma[p][i]==j) continue;
          flg=ma[p][i];break;
        }
        if(!flg) continue;
        tmp+=a[flg];ll flgg=0;
        for(ll p=1;p<=3;p++) {
          if(ma[p][j]<=1) continue;
          if(ma[p][j]==i||ma[p][j]==flg) continue;
          flgg=ma[p][j];break;
        }
        if(!flgg) continue;
        tmp+=a[flgg];
//        printf("test:%lld %lld %lld %lld\n",flg,i,j,flgg);
        ans=max(tmp,ans);
      }
    }
  }
  
  write(ans);
  
  return 0;
}