Problem

一个机器人在一张n个点m条边的有向无环图上行走，每天等概率地在原地不动或者移动到相邻的位置

每天消耗的能量为已经过去的天数，问从起点抵达终点最小耗能

$2 \le n \le 10^5,1 \le m \le 2 \ast 10^5$

Solution

因为从起点出发到终点转移是等概率的，所以考虑按照从终点到起点的拓扑序转移

记$g_u$为$u$点到终点的期望步数，$f_u$为$u$点到终点的期望代价

考虑在路径序列前端多加一个点，其之后每一天的代价都会增加1

那么其和有向图上的后继节点关系有：

$g_u=(\sum(g_v+1)+g_u+1)/(sz_u+1)$

$f_u=(\sum(f_v+g_v+1)+f_u+g_u+1)/(sz_u+1)$

按照从终点到起点拓扑序转移计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int T, n, m;
vector<int> ret, v[N], G[N];
double g[N], f[N];
int d[N];
void TopSort() {
    queue<int> Q;
    Q.push(n);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        ret.push_back(u);
        for (auto x : v[u]) {
            --d[x];
            if (!d[x]) Q.push(x);
        }
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) G[i].clear(), v[i].clear();
        ret.clear();
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            v[y].push_back(x);
            G[x].push_back(y);
            d[x]++;
        }
        TopSort();
        for (int x : ret) {
        	f[x] = 0;
        	g[x] = 0; 
            if (!G[x].size()) continue;
            for (int y : G[x]) {
                g[x] = g[x] + g[y] + 1;
                f[x] = f[x] + f[y] + g[y] + 1;
            }
            g[x] = (g[x] + 1) / G[x].size();
            f[x] = (f[x] + g[x] + 1) / G[x].size();
        }
        printf("%.2f\n", f[1]);
    }
    return 0;
}