狩猎（2021 CoE-II D）

· · 题解

题目链接

本题的底层模型是无向图上的概率动态规划。

每个状态有三个参数：当前所在顶点 u，已经消耗的体力 h，已经花费的时间 t。令 hp[u][h][t] 表示在顶点 u，已经消耗的体力为 h，已经花费的时间为 t 时消耗体力的期望值（即平均值），elapsed[u][h][t] 表示在顶点 u，已经消耗的体力为 h，已经花费的时间为 t 时花费时间的期望值（即平均值），根据题目给定的规则进行状态转移，所求即 hp[0][0][0]，elapsed[0][0][0]。读者可结合参考代码的注释进行理解。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x7f7f7f7f;

// 表示无向图中边的数据结构，v 为邻接顶点的编号，h 为消耗的体力，t 为花费的时间
struct edge
{
    int v, h, t;
    edge (int v = 0, int h = 0, int t = 0): v(v), h(h), t(t) {}
    // 重载小于运算符以使用优先队列
    bool operator<(const edge &e) const { return t != e.t ? t > e.t : h > e.h; }
};

// p[i] 表示第 i 个狩猎点捕获猎物的概率，
// hp[i][j][k] 和 elapsed[i][j][k] 的意义如前所述
double p[210], hp[210][260][260], elapsed[210][260][260];

// visited 为标记数组，标记某个状态是否已经访问
int visited[210][260][260];
vector<edge> edges[210];

// dH[i] 表示从地点 i 回到巢穴的符合要求的路径所消耗的体力
// dT[i] 表示从地点 i 回到巢穴的符合要求的路径所花费的时间
// neighbours[i] 表示顶点 i 所邻接的狩猎点个数
// hi[i] 表示在第 i 个地点进行一次捕猎所消耗的体力
// ti[i] 表示在第 i 个地点进行一次捕猎所花费的时间
// 很明显，在巢穴无法进行捕猎，故 hi[0] = ti[0] = 0
int N, M, H, T, dH[210], dT[210], neighbours[210], hi[210], ti[210];

// u 为当前所在的顶点，h 为已经消耗的体力，t 为已经花费的时间
void dfs(int u, int h, int t)
{
    // 备忘以加快求解速度，否则会超时
    if (visited[u][h][t]) return;
    visited[u][h][t] = 1;
    hp[u][h][t] = elapsed[u][h][t] = 0;
    // 如果当前是狩猎点
    if (u)
    {
        // 有 p[u] 的概率在该狩猎点捕猎成功，直接返回巢穴结束狩猎
        hp[u][h][t] += p[u] * (h + dH[u]);
        elapsed[u][h][t] += p[u] * (t + dT[u]);

        // 若不成功，检查体力和时间是否超出限制，如果超出，直接选择返回巢穴
        if (h >= H || t >= T)
        {
            hp[u][h][t] += (1 - p[u]) * (h + dH[u]);
            elapsed[u][h][t] += (1 - p[u]) * (t + dT[u]);
            return;
        }

        // 当狩猎不成功且体力和和时间均未超出限制时，
        // 如果当前狩猎点与其他狩猎点无直连双向道路则
        // 返回巢穴，更新期望体力和时间，注意是转移到
        // 巢穴后再更新
        if (!neighbours[u])
        {
            dfs(0, h + dH[u], t + dT[u]);
            hp[u][h][t] += (1 - p[u]) * hp[0][h + dH[u]][t + dT[u]];
            elapsed[u][h][t] += (1 - p[u]) * elapsed[0][h + dH[u]][t + dT[u]];
        }
        // 当前狩猎点与其他狩猎点有直连双向道路，随机选择一个狩猎点进行状态转移
        else
        {
            double s = 1.0 / neighbours[u];
            for (auto e : edges[u])
            {
                // 确保是狩猎点而不是巢穴
                if (e.v)
                {
                    dfs(e.v, h + e.h + hi[e.v], t + e.t + ti[e.v]);
                    hp[u][h][t] += s * (1 - p[u]) * hp[e.v][h + e.h + hi[e.v]][t + e.t + ti[e.v]];
                    elapsed[u][h][t] += s * (1 - p[u]) * elapsed[e.v][h + e.h + hi[e.v]][t + e.t + ti[e.v]];
                }
            }
        }
    }
    // 当前位于巢穴
    else
    {
        // 体力或者时间超出限制
        if (h >= H || t >= T)
        {
            hp[u][h][t] = h + dH[u];
            elapsed[u][h][t] = t + dT[u];
            return;
        }
        // 如果有狩猎点与巢穴相邻，随机选择一个狩猎点进行状态转移
        if (neighbours[u])
        {
            double s = 1.0 / neighbours[u];
            for (auto e : edges[u])
            {
                dfs(e.v, h + e.h + hi[e.v], t + e.t + ti[e.v]);
                hp[u][h][t] += s * hp[e.v][h + e.h + hi[e.v]][t + e.t + ti[e.v]];
                elapsed[u][h][t] += s * elapsed[e.v][h + e.h + hi[e.v]][t + e.t + ti[e.v]];
            }
        }
    }
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> hi[i] >> ti[i] >> p[i];
    for (int i = 0; i <= N; i++)
    {
        edges[i].clear();
        neighbours[i] = 0;
    }
    cin >> M;
    for (int i = 0, u, v, h, t; i < M; i++)
    {
        cin >> u >> v >> h >> t;
        edges[u].push_back(edge(v, h, t));
        edges[v].push_back(edge(u, h, t));
        // 确定每个顶点有多少个狩猎点与之相邻
        neighbours[u] += (v > 0);
        neighbours[v] += (u > 0);
    }
    cin >> H >> T;

    // 确定每个地点返回巢穴时具有最短时间的路径，
    // 如果有多条具有最短时间的路径，选择消耗体力
    // 最少的路径
    memset(dH, INF, sizeof dH);
    memset(dT, INF, sizeof dT);
    priority_queue<edge> q;
    dH[0] = dT[0] = 0;
    q.push(edge(0, 0, 0));
    while (!q.empty())
    {
        edge e1 = q.top();
        q.pop();
        if (dT[e1.v] < e1.t) continue;
        for (auto e2 : edges[e1.v])
        {
            if (dT[e2.v] > dT[e1.v] + e2.t || 
                (dT[e2.v] == dT[e1.v] + e2.t && dH[e2.v] > dH[e1.v] + e2.h))
            {
                dT[e2.v] = dT[e1.v] + e2.t;
                dH[e2.v] = dH[e1.v] + e2.h;
                q.push(edge(e2.v, dH[e2.v], dT[e2.v]));
            }
        }
    }

    // 递归加备忘确定期望值
    memset(visited, 0, sizeof(visited));               
    dfs(0, 0, 0);
    cout << fixed << setprecision(1) << hp[0][0][0] << ' ' << elapsed[0][0][0] << '\n';

    return 0;
}