CF679D Bear and Chase
本题题解
记图的边集为 \(E\)。
先用 floyd 算法预处理出任意两点之间的距离。时间复杂度 \(\mathcal{O}(n^3)\)。
记两次查询的节点分别为 \(a\), \(b\)，两次查询得到的结果分别为 \(d_1, d_2\)。
- 枚举 \(a\)。计算出第一步选 \(a\) 时的答案。因为我们要求最优策略下的答案，所以对所有 \(a\) 的情况取最大值即可。
- 枚举 \(d_1\)。考虑所有距离 \(a\) 为 \(d_1\) 的节点，记为点集 \(U = \{u | \mathrm{dis}(u, a) = d_1\}\)。则得到回答 "\(d_1\)" 的概率是 \(\frac{|U|}{n}\)。求出 \(d_1\) 的答案后，乘以这个概率，累加起来，就是当前 \(a\) 的答案了。
- 预处理出第二天罪犯来到 \(v\) 的概率 \(p(v)\)。具体来说，\(p(v) = \sum_{u\in U} \frac{1}{|U|}\cdot \frac{1}{\mathrm{deg(u)}} \cdot[(u, v)\in E]\)。把所有 \(p(v)\neq 0\) 的点（即与 \(U\) 中至少一个点有连边的点）存起来，记为集合 \(V = \{v | p(v)\neq 0\}\)。
- 现在已经得到了回答 \(d_1\)。考虑我们接下来的最优策略，是两种情况的较大者：要么在 \(U\) 中随便猜一个点，并结束游戏，获胜的概率是 \(\frac{1}{|U|}\)。要么继续询问。
- 如果继续询问。枚举接下来要询问的点 \(b\)。那这种情况下，获胜的概率就是所有 \(b\) 的答案的最大值。对每个 \(b\)：
- 枚举得到的回答 \(d_2\)。考虑距离 \(b\) 为 \(d_2\) 的点，记为集合 \(W = \{w | \mathrm{dis}(w, b) = d_2\}\)。在知道了 \(d_2\) 后，我们有唯一的最优策略，且获胜的概率是 \(\frac{\max_{v \in (V \cap W)}\{p(v)\}}{\sum_{v\in(V \cap W)} p(v)}\)。同时，\(d_2\) 发生的概率是 \(\sum_{v\in(V \cap W)} p(v)\)。所以 \(b\) 的答案是：\(\sum_{d_2} \frac{\max_{v \in (V \cap W)}\{p(v)\}}{\sum_{v\in(V \cap W)} p(v)}\times (\sum_{v\in(V \cap W)} p(v)) = \max_{v \in (V \cap W)}\{p(v)\}\)。所以我们只需要在枚举 \(d_2\) 之前，先枚举一遍 \(v\)，就能预处理出每个 \(d_2\) 的答案。然后再扫描所有 \(d_2\)，把这些答案加起来。
- 枚举 \(d_1\)。考虑所有距离 \(a\) 为 \(d_1\) 的节点，记为点集 \(U = \{u | \mathrm{dis}(u, a) = d_1\}\)。则得到回答 "\(d_1\)" 的概率是 \(\frac{|U|}{n}\)。求出 \(d_1\) 的答案后，乘以这个概率，累加起来，就是当前 \(a\) 的答案了。
上述的做法看起来是四重循环。但对于同一个 \(a\)，在所有 \(d_1\) 下 \(U\) 集合的大小之和为 \(n\)。\(V\) 集合里的点与 \(a\) 的距离要么是 \(d_1 + 1\)，要么是 \(d_1 - 1\)，所以 \(V\) 集合的大小之和也是 \(\mathcal{O}(n)\) 的。发现我们真正枚举的只有 \(a, b, V\)，时间复杂度是 \(\mathcal{O}(n^3)\) 的。
具体可以见代码。
参考代码
// problem: CF679D
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 400;
const int INF = 1e9;
int n, m;
vector<int> G[MAXN + 5];
int dis[MAXN + 5][MAXN + 5];
double p[MAXN + 5];
bool vis[MAXN + 5];
vector<int> calc_probability_for_each_city(const vector<int>& vec_u) {
for (int i = 1; i <= n; ++i) {
p[i] = 0;
vis[i] = 0;
}
vector<int> vec_v;
for (int i = 0; i < SZ(vec_u); ++i) {
int u = vec_u[i];
for (int j = 0; j < SZ(G[u]); ++j) {
int v = G[u][j];
p[v] += 1.0 / SZ(vec_u) / SZ(G[u]);
if (!vis[v]) {
vis[v] = 1;
vec_v.push_back(v);
}
}
}
return vec_v;
}
double pmax[MAXN + 5];
double consider_tomorrow(const vector<int>& vec_v) {
double res = 0;
for (int i = 0; i < n; ++i) {
pmax[i] = 0;
}
for (int b = 1; b <= n; ++b) { // 第二次询问的节点
// 选好 b 后, 会问到一个距离 d2
// 我们根据 d2 去选择最终的猜测: c. 即: 每个 d2 对应了一种选 c 的策略
// 具体来说就是选择该 d2 里概率 p 最大的点作为 c
// 所以此处先对每种距离 d2, 预处理出它对应的节点的 p 的最大值
for (int i = 0; i < SZ(vec_v); ++i) {
int v = vec_v[i];
ckmax(pmax[dis[v][b]], p[v]);
}
double res_b = 0;
for (int i = 0; i < SZ(vec_v); ++i) {
int v = vec_v[i];
int d2 = dis[v][b];
res_b += pmax[d2];
pmax[d2] = 0;
}
ckmax(res, res_b);
}
return res;
}
double ask_immediately(const vector<int>& vec_u) {
return 1.0 / SZ(vec_u);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dis[i][j] = (i == j ? 0 : INF);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
dis[u][v] = dis[v][u] = 1;
}
for (int k = 1; k <= n; ++k) { // 中间点
for (int i = 1; i <= n; ++i) { // 起点
for (int j = 1; j <= n; ++j) { // 终点
ckmin(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
double ans = 0;
for (int a = 1; a <= n; ++a) { // 第一次询问的节点
double ans_a = 0;
for (int d1 = 0; d1 < n; ++d1) { // 第一次得到的答案
vector<int> vec_u;
double p_d1 = 0;
for (int u = 1; u <= n; ++u) if (dis[a][u] == d1) {
vec_u.push_back(u);
p_d1 += 1;
}
if (!SZ(vec_u))
continue;
p_d1 /= (double)n;
double ans_a_d1 = 0;
vector<int> vec_v = calc_probability_for_each_city(vec_u);
ans_a_d1 = max(consider_tomorrow(vec_v), ask_immediately(vec_u));
ans_a += p_d1 * ans_a_d1; // 有 p 的概率, 进入 d1 这种情况
// 在 d1 的情况下, 选取最优策略能得到 ans_a_d1 这一答案
}
ckmax(ans, ans_a); // 选取最优策略
}
cout << setiosflags(ios :: fixed) << setprecision(10) << ans << endl;
return 0;
}