简答题
偏难
#22094
假期计划(holiday)
假期计划(holiday)



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int cp = 998244353;
inline int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1ll * a * a % cp) {
if (b & 1) {
ret = 1ll * ret * a % cp;
}
}
return ret;
}
inline int inv(int x) {
return ksm(x, cp - 2);
}
inline int rev(int p, int q) {
return 1LL * p * inv(q) % cp;
}
const int N = 2505;
int n, m, K, pos[N][3], f[N][N];
ull a[N], ans;
vector<int> G[N];
queue<int> Q;
void bfs(int S) {
f[S][S] = 1;
Q.push(S);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (auto v : G[x]) {
if (f[S][v] < 0) {
f[S][v] = f[S][x] + 1;
Q.push(v);
}
}
}
}
void check(int A, int B, int C, int D) {
if (!A || !B || !C || !D) return;
if (A == B || A == C || A == D || B == C || B == D || C == D) return;
if (f[1][A] > K || f[A][B] > K || f[B][C] > K || f[C][D] > K || f[D][1] > K) return;
ans = max(ans, a[A] + a[B] + a[C] + a[D]);
}
signed main() {
memset(f, -1, sizeof(f));
n = read(), m = read(), K = read() + 2;
for (int i = 2; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1, x, y; i <= m; ++i) {
x = read(), y = read();
G[x].push_back(y);
G[y].push_back(x);
}
bfs(1);
for (int i = 2; i <= n; ++i) {
bfs(i);
for (int j = 2; j <= n; ++j) {
if (f[i][j] != -1 && f[1][j] != -1 && f[i][j] <= K && f[1][j] <= K && i != j) {
int x = j;
if (a[x] > a[pos[i][0]]) swap(x, pos[i][0]);
if (a[x] > a[pos[i][1]]) swap(x, pos[i][1]);
if (a[x] > a[pos[i][2]]) swap(x, pos[i][2]);
}
}
}
for (int B = 2; B <= n; ++B) {
for (int C = 2; C <= n; ++C) {
if (B != C && f[B][C] <= K && f[B][C] != -1) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
check(pos[B][i], B, C, pos[C][j]);
}
}
}
}
}
cout << ans;
return 0;
}</pre><p><br/></p>
这道题暂未补解析。