题解 P8817【[CSP-S 2022] 假期计划】

yukimianyan · 2022-10-29 23:32:15 · 题解

problem

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;
}