题解：迷宫步数期望值计算

算法思路

本题需要计算从起点 $s$ 到终点 $t$ 的期望步数，采用以下方法：

1. 强连通分量分解

• 使用 Tarjan 算法 将原图分解为强连通分量（SCC）
• 按拓扑逆序处理每个 SCC（从终点所在 SCC 开始）

2. 期望步数计算

对于每个 SCC：

• 如果 SCC 包含终点 $t$，设置 $res[t] = 0$
• 对于 SCC 中的每个节点 $u$：
  • 如果 $u = t$，期望步数为 $0$
  • 否则，建立线性方程：$$res[u] = 1 + \sum_{v \in g[u]} \frac{res[v]}{outdeg(u)} $$

3. 高斯消元

• 对每个 SCC 建立线性方程组
• 使用高斯消元法求解节点期望步数
• 处理无穷大情况（不可达或存在环）

代码实现

#include <bits/stdc++.h>
using namespace std;

// 全局变量定义
int dfn[10001], id[10001], rnk[10001], low[10001], clk, cnt;
double res[10001], w[101][101], equ[101], val[101];
bool vis[10001];
vector<int> g[10001], scc[10001];
stack<int> st;

// Tarjan 算法求强连通分量
void tarjan(int x) {
    clk++;
    dfn[x] = low[x] = clk;
    st.push(x);

    for (int i : g[x]) {
        if (vis[i]) continue;
        
        if (!dfn[i]) {
            tarjan(i);
            low[x] = min(low[x], low[i]);
        } else {
            low[x] = min(low[x], dfn[i]);
        }
    }

    if (dfn[x] == low[x]) {
        cnt++;
        while (st.top() != x) {
            scc[cnt].push_back(st.top());
            id[st.top()] = cnt;
            rnk[st.top()] = scc[cnt].size();
            vis[st.top()] = true;
            st.pop();
        }
        scc[cnt].push_back(x);
        id[st.top()] = cnt;
        rnk[st.top()] = scc[cnt].size();
        st.pop();
        vis[x] = true;
    }
}

// 高斯消元法求解线性方程组
void gauss(int n) {
    for (int i = 1; i <= n; i++) {
        // 寻找主元
        for (int j = i; j <= n; j++) {
            if (w[j][i] != 0) {
                swap(w[i], w[j]);
                swap(equ[i], equ[j]);
                break;
            }
        }

        // 消元
        for (int j = 1; j <= n; j++) {
            if (j == i) continue;
            
            double c = w[j][i] / w[i][i];
            for (int k = 1; k <= n; k++) {
                w[j][k] -= c * w[i][k];
            }
            equ[j] -= c * equ[i];
        }
    }

    // 回代求解
    for (int i = 1; i <= n; i++) {
        val[i] = equ[i] / w[i][i];
    }
}

int main() {
    int n, m, s, t;
    scanf("%d %d %d %d", &n, &m, &s, &t);

    // 读入图
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
    }

    // Tarjan 算法求 SCC
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            tarjan(i);
        }
    }

    // 初始化结果数组
    for (int i = 1; i <= n; i++) {
        res[i] = __builtin_inf();
    }

    // 按拓扑逆序处理每个 SCC
    for (int i = id[t]; i <= cnt; i++) {
        // 初始化方程组的系数矩阵和常数项
        for (int j = 1; j <= scc[i].size(); j++) {
            for (int k = 1; k <= scc[i].size(); k++) {
                w[j][k] = 0;
            }
            equ[j] = 0;
        }

        bool flag = true;

        // 建立线性方程组
        for (int j : scc[i]) {
            if (j == t) {
                // 终点期望步数为 0
                equ[rnk[t]] = 0;
                w[rnk[t]][rnk[t]] = 1;
                continue;
            } else if (g[j].empty()) {
                // 无出边，不可达
                flag = false;
                break;
            }

            equ[rnk[j]] = 1;  // 常数项
            w[rnk[j]][rnk[j]] = 1;  // 系数矩阵对角线

            // 处理所有出边
            for (int k : g[j]) {
                if (id[k] < id[j]) {
                    // 拓扑序更小的分量，使用已知结果
                    equ[rnk[j]] += res[k] / g[j].size();
                } else {
                    // 同一分量内，建立方程关系
                    w[rnk[j]][rnk[k]] -= 1.0 / g[j].size();
                }
            }
        }

        if (!flag) {
            // 该 SCC 不可达终点
            for (int j : scc[i]) {
                res[j] = __builtin_inf();
            }
            continue;
        }

        // 高斯消元求解
        gauss(scc[i].size());

        // 更新结果
        for (int j : scc[i]) {
            res[j] = val[rnk[j]];
        }
    }

    // 输出结果
    if (res[s] == __builtin_inf() || isnan(res[s])) {
        printf("INF\n");
    } else {
        printf("%.3lf\n", res[s]);
    }

    return 0;
}

关键点分析

1. 拓扑逆序处理：从终点所在 SCC 开始，确保依赖关系正确
2. 线性方程组建立：根据期望步数的定义建立方程
3. 高斯消元：求解 SCC 内部的期望步数
4. 边界处理：
   • 终点 $t$ 的期望步数为 $0$
   • 无出边的节点期望步数为无穷大
   • 不可达情况输出 INF

复杂度分析

• 时间复杂度：$O(n^3)$，主要来自高斯消元
• 空间复杂度：$O(n^2)$，存储图结构和系数矩阵

该算法充分利用了 SCC 分解和拓扑排序的性质，有效处理了图中可能存在的环结构。