洛谷P8817 [CSP-S 2022] 假期计划题解

题目链接：P8817 [CSP-S 2022] 假期计划

题意：

小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。

很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A \(\to\) 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D \(\to\) 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

输入格式：

第一行包含三个正整数 \(n, m, k\)，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 \(n - 1\) 个正整数，分别表示编号为 \(2, 3, \ldots, n\) 的景点的分数。

接下来 \(m\) 行，每行包含两个正整数 \(x, y\)，表示点 \(x\) 和 \(y\) 之间有道路直接相连，保证 \(1 \le x, y \le n\)，且没有重边，自环。

输出格式：

输出一个正整数，表示小熊经过的 \(4\) 个不同景点的分数之和的最大值。

数据范围：

保证 \(5 \le n \le 2500\)，\(1 \le m \le 10000\)，\(0 \le k \le 100\) 。

所有景点的分数 \(1 \le s_i \le {10}^{18}\)。保证至少存在一组符合要求的行程。

考场上 5 min 糊了一个 dp ，调了两个多小时还是过不了大样例，结果拿了 55pts 。

至今不知道错在了什么地方，总之那个方法是对标 85pts 的。

这题是贪心。注意到这题最可疑的地方就是这个景点只有 \(4\) 个，而且不可重。

如果我们枚举 \(3\) 个景点，那么第 \(4\) 个景点可以通过 \(\mathcal{O}(n^2)\) 预处理得到。

设这几个景点分别为 \(a,b,c,d\) ，上面的做法就是枚举 \(a,b,c\) 。

那么能不能找到更快的方法呢？如果我们枚举 \(a,b\) ，贪心并不能算出正确的 \(c,d\) 。

但是如果我们枚举 \(b,c\) ，就可以确定出 \(a,d\) （注意要算个 \(k(k\le 3)\) 近点，反正重点）

然后这题就没了，时间复杂度 \(\mathcal{O}(cn^2),~c \le 10\) 为 \(k\) 近点多出的复杂度

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2515))
#define M ((int)(1e4 + 15))

int n,m,k,pos=1,val[N],dis[N],head[N];
struct Edge { int u,v,next; } e[M * 2];
bitset<N> ok[N]; vector<int> f[N]; queue<int> q;
bool cmp(int a,int b) { return val[a] > val[b]; }
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void bfs(int s)
{
    for(int i=1; i<=n; i++) dis[i] = -1;
    while(!q.empty()) q.pop();
    for(q.push(s),dis[s] = 0; !q.empty(); )
    {
        int u = q.front(); q.pop();
        if(u != s)
        {
            ok[s][u] = 1;
            if(s != 1 && ok[1][u])
            {
                f[s].push_back(u);
                sort(f[s].begin(), f[s].end(), cmp);
                if(f[s].size() > 3) f[s].pop_back();
            }
        }
        if(dis[u] == k + 1) continue;
        for(int i = head[u]; i; i=e[i].next)
        {
            int v = e[i].v; if(dis[v] != -1) continue;
            dis[v] = dis[u] + 1; q.push(v);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    cin >> n >> m >> k;
    for(int i=2; i<=n; i++) cin >> val[i];
    for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    for(int i=1; i<=n; i++) bfs(i); int res = 0;
    for(int b=2; b<=n; b++)
        for(int c=2; c<=n; c++) if(ok[b][c])
            for(int a : f[b]) for(int d : f[c])
                if(a != c && b != d && a != d) up(res, val[a] + val[b] + val[c] + val[d]);
    cout << res << '\n';
    return 0;
}