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