CSP2022 假期计划 题解

给你一张 \(n\) 个点, \(m\) 条边的无向图, 每个点有点权, 要求你在图中选出 \(A\), \(B\), \(C\), \(D\) 四个点, 使得 \(1\rightarrow A\rightarrow B\rightarrow C\rightarrow D\rightarrow 1\) 中, 前一个点到后一个点距离不超过 \(k\) 条边, 并且四个点点权之和最大

算法1

测试点 \(1\sim 8\) 满足 \(n\le 30\), 可以直接枚举 \(A, B, C, D\) 四个点, 时间复杂度 \(O(n^4)\), 期望得分 \(40\rm {pts}\)

算法2

考虑减少枚举的点的数量, 如果 \(A, B, C\) 已经确定, 那么 \(D\) 就可以不用枚举了, 直接取在 \(C\) 的 \(k\) 步之内并且在 \(1\) 的 \(k\) 步之内并且没有被取过的最大值(通过预处理一个点可达并且从 \(1\) 可达的前三大)即可, 这一步需要预处理出每个点到其他所有点的距离, 因为没有边权所以可以 \(O(N^2)\) 解决, 时间复杂度 \(O(n^3)\), 期望得分 \(70\rm {pts}\)

算法3

可以发现, 只要 \(C\) 点固定了 \(D\) 点就是固定的, 所以考虑用同样的方法维护 \(A\) 点, 只要 \(B\) 固定了 \(A\) 同样是固定的, 类似上面即可, 时间复杂度 \(O(n^2)\), 期望得分 \(100\rm {pts}\)

#include <bits/stdc++.h>

using namespace std;
const int N = 2510, M = 2e4 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<long long, int> PII;
int e[M], ne[M], h[N], G[N][N], idx;
long long w[N];
PII f[N][3];
bool st[N];
int n, m, k;

inline void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], h[b] = idx++;
}

bool cmp(PII a, PII b){
    return a.first > b.first;
}

void bfs(int z){
    queue<int> q;
    q.push(z);
    G[z][z] = -1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(G[z][v] != inf)
                continue;
            
            G[z][v] = G[z][u] + 1;
            q.push(v);

            //如果这个点在家附近并且从这个点出发可以到达
            if(st[v] && G[z][v] <= k){
                PII tmp[4];
                for(int i = 0; i < 3; i++)
                    tmp[i] = f[z][i];
                tmp[3].first = w[v];
                tmp[3].second = v;
                sort(tmp, tmp + 4, cmp);
                for(int i = 0; i < 3; i++)
                    f[z][i] = tmp[i];
            }
        }
    }
    
}

int main(){
    memset(h, -1, sizeof h);
    memset(G, 0x3f, sizeof G);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 2; i <= n; i++){
        scanf("%lld", &w[i]);
    }
    for(int i = 1; i <= m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++)
            f[i][j] = {-1, 0};
    }
    
    st[1] = false;
    queue<int> q;
    q.push(1);
    G[1][1] = -1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(G[1][v] != inf)
                continue;

            G[1][v] = G[1][u] + 1;
            q.push(v);

            if(G[1][v] <= k)
                st[v] = true;
        }
    }

    for(int i = 2; i <= n; i++){
        bfs(i);
    }
    
    long long ans = -1;
    for(int b = 2; b <= n; b++){
        for(int c = 2; c <= n; c++){
            if(G[b][c] > k || b == c)
                continue;
            for(int i = 0; i < 3; i++){
                int a = f[b][i].second;
                if(a == 0) 
                    break;
                for(int j = 0; j < 3; j++){
                    int d = f[c][j].second;
                    if(d == 0)
                        break;
                    if(d == a || b == c || a == c || d == b)
                        continue;
                    ans = max(ans, w[a] + w[b] + w[c] + w[d]);
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}