posted on 2022-10-29 23:32:15 | under 题解 | source
problem
\(n\) 个点 \(m\) 条边的无向无权图，令 \(to(i,j)=[\operatorname{dist}(i,j)\leq k+1]\)，点带权 \(a_i\)，求：
\[[*]=\max_{A\neq B\neq C\neq D\neq 1}to(1,A)\cdot to(A,B)\cdot to(B,C)\cdot to(C,D)\cdot to(D,1)\cdot(a_A+a_B+a_C+a_D). \]\(n,m\leq 3000.\)
solution
以每个点为源点跑 bfs，求出 \(to(i,j)\)，复杂度 \(O(nm)\)。
我们弱化一下这个问题：如果只有两个景点 \(A,B\)，怎么做？
我们可以预处理一个 \(F_{i,j}\) 表示一个权值最大的景点 \(k\) 满足 \(to(i,k)\land to(k,j)\)，我们先不说怎么做。然后枚举景点 \(A\)，那么我们确信景点 \(F_{1,A}\) 是最优的。
现在我们有三个景点 \(A,B,C\)，我仍然可以枚举 \(B\)，转移 \(F_{1,i}\) 的时候记录最大值和次大值，那么我们确信这两个值是 \(A,C\) 的最优取值。
现在我们有四个景点 \(A,B,C,D\)，我们可以枚举 \(B,C\)，用 \(F_{1,B},F_{C,1}\) 分别求出 \(A,D\) 的最优取值。注意当我们确定 \(F_{1,B}\) 时，有两个景点（\(B,F_{1,B}\)）已经被选，所以使用 \(F_{C,1}\) 时我们要记录最大值、次大值、次次大值，确保没有重复才能转移。反过来也要判一次。枚举的复杂度是 \(O(n^2)\) 的。
现在回到 \(F\)，我们发现，由于图是无向图，因此我们断定 \(F_{i,j}=F_{j,i}\)，这样一来我们所有用到的 \(F\) 都形如 \(F_{1,i}\)，状态数 \(O(n)\)，转移暴力 \(O(n)\) 就好了。
code
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<int N,int M,class T=int> struct graph{
int head[N+10],nxt[M*2+10],cnt;
struct edge{
int u,v; T w;
edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
} e[M*2+10];
graph(){memset(head,cnt=0,sizeof head);}
edge& operator[](int i){return e[i];}
void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
LL a[3010];
bool cmp(int i,int j){return a[i]>=a[j];}
struct node{
int v[4];
node(){v[0]=v[1]=v[2]=v[3]=0;}
void update(int k){
if(cmp(k,v[0])) v[3]=v[2],v[2]=v[1],v[1]=v[0],v[0]=k;
else if(cmp(k,v[1])) v[3]=v[2],v[2]=v[1],v[1]=k;
else if(cmp(k,v[2])) v[3]=v[2],v[2]=k;
else if(cmp(k,v[3])) v[3]=k;
}
int operator[](int i){return v[i];}
};
int n,m,sshwy,dis[3010];
bool to[3010][3010];
graph<3010,10010> g;
void bfs(int s){
queue<int> q;
memset(dis,0x3f,sizeof dis);
for(q.push(s),dis[s]=0;!q.empty();){
int u=q.front(); q.pop();
if(dis[u]>sshwy+1) continue;
to[s][u]=1;
if(dis[u]==sshwy+1) continue;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(dis[v]>dis[u]+1) dis[v]=dis[u]+1,q.push(v);
}
}
}
node f[3010];
void dp(){
for(int i=2;i<=n;i++){
for(int j=2;j<=n;j++){
if(i==j||!to[1][i]||!to[i][j]) continue;
f[j].update(i);
}
}
// for(int i=1;i<=n;i++){
// fprintf(stderr,"f[%d]={%d,%d,%d,%d}\n",i,f[i][0],f[i][1],f[i][2],f[i][3]);
// }
}
LL solve(){
LL res=-1;
for(int u=2;u<=n;u++){
for(int v=2;v<=n;v++){
if(!to[u][v]) continue;
node &be=f[u],&ce=f[v];
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(!be[i]||!ce[j]) continue;
int pos[]={u,v,be[i],ce[j]};
if(sort(pos,pos+4),unique(pos,pos+4)==pos+4){
res=max(res,a[u]+a[v]+a[be[i]]+a[ce[j]]);
break;//后面的决策不会更优
}
}
}
//考场并没有发现只需要 3 个值，写的比较暴力
}
}
return res;
}
int main(){
a[0]=a[1]=-1e18;
freopen("holiday.in","r",stdin),freopen("holiday.out","w",stdout);
scanf("%d%d%d",&n,&m,&sshwy);
for(int i=2;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),g.link(u,v);
for(int i=1;i<=n;i++) bfs(i);
dp();
printf("%lld\n",solve());
return 0;
}