Hellc

【题目描述】

一个无向连通图，顶点从 1 编号到 N ，边从 1 编号到 M 。

小Z 在该图上进行随机游走，初始时 小Z 在 1 号顶点，每一步 小Z 以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当 小Z 到达 N 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 M 条边进行编号，使得 小Z 获得的总分的期望值最小。

【题目链接】

BZOJ 3143 游走 【HNOI 2013】

【解题思路】

由于标号方案与边的期望贡献无关，所以可以先计算边的期望贡献，然后贪心地标号，即对最大的边标号 $1$，次大的边标号 $2$ …… 最小的边标号 $m$。

一条边的期望贡献为经过该边的期望次数乘上边权，所以下面的任务是求经过某边的期望次数。

类似 [BZOJ 3036] 绿豆蛙的归宿 - 期望DP，我们可以由点的期望来计算边的期望。

设 $e_i$ 为经过点 $i$ 的期望次数，$d_i$ 为点 $i$ 的度，那么对于一条边 $(u, v), v \not= n$，经过其的期望次数为 $e_u \times \frac 1 d_u + e_v \times \frac 1 d_v$，即考虑从 $u$ 或 $v$ 经过这条边。

特别的，对于 $(u, n)$ 的边，经过其的期望次数为 $e_u \times \frac 1 d_u$，这是因为我们走到 $n$ 就结束了。

下面考虑怎么求 $e_i$，因为图不是 DAG，所以无法递推，只能通过高斯消元解方程组来求。

我们试着列出方程组：

（$p_{x, y}$ 表示从 $x$ 走到 $y$ 的概率）

对于起点 1 ： $$ e_1 = 1 + \sum_{1 \lt j \lt n}e_j \times p_{j, i} $$

加 1 是因为一开始就经过了一次。

对于其他点 $i$ : $$ e_i = \sum_{1 \leq j \lt n,j \not= i}e_j \times p_{j, i} $$

为了解方程，我们把未知数移到一边，化为一般形式：

对于起点 1 ： $$ -e_1 + \sum_{1 \lt j \lt n}e_j \times p_{j, i} = -1 $$

对于其他点 $i$ : $$ -e_i + \sum_{1 \leq j \lt n,j \not= i}e_j \times p_{j, i} = 0 $$

高斯消元把这个方程组解出来即可。

至于求 $p_{x, y}$，如果 $x, y$ 有边，那么 $p_{x, y} = \frac 1 d_x$，否则 $p_{x, y} = 0$。

总结：图上求期望的一般思路，将边的期望转化为点的期望，使用递推（DAG）或高斯消元（一般图）求解。

【AC代码】

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cassert>
 
const int MAXN = 500;
const int MAXM = MAXN * (MAXN - 1) / 2;
 
bool G[MAXN][MAXN];
int deg[MAXN];
int n, m;
 
inline void link(int u, int v){
    G[u][v] = G[v][u] = true;
    deg[u]++, deg[v]++;
}
 
double a[MAXN][MAXN + 1 + 1];
 
inline void buildEquations(){
    for(int i = 0; i < n; i++) a[i][i] = -1;
    a[0][n] = -1;
    for(int i = 0; i < n - 1; i++) for(int j = 0; j < n; j++) if(G[i][j]){
        a[j][i] += 1.0 / deg[i];
    }
}
 
inline void guassJordan(){
    for(int i = 0; i < n; i++){
        int p = i;
        for(int j = i + 1; j < n; j++) if(std::fabs(a[j][i]) > std::fabs(a[p][i])) p = j;
        if(p != i) for(int j = i; j <= n; j++) std::swap(a[i][j], a[p][j]);
 
        assert(std::fabs(a[i][i]) >= 1e-10);
 
        for(int j = 0; j < n; j++) if(i != j){
            for(int k = n; k >= i; k--){
                a[j][k] -= a[i][k] / a[i][i] * a[j][i];
            }
        }
    }
}
 
double exNode[MAXN], exEdge[MAXM];
 
inline double solve(){
    buildEquations(), guassJordan();
    for(int i = 0; i < n; i++) exNode[i] = a[i][n] / a[i][i];
 
    int p = 0;
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) if(G[i][j]){
        exEdge[p] += exNode[i] / deg[i];
        if(j != n - 1) exEdge[p] += exNode[j] / deg[j];
 
        p++;
    }
 
    std::sort(exEdge, exEdge + m);
 
    double ans = 0;
    for(int i = 0; i < m; i++) ans += exEdge[i] * (m - i);
    return ans;
}
 
int main(){
    std::cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        std::cin >> u >> v, u--, v--;
 
        link(u, v);
    }
 
    std::cout << std::fixed << std::setprecision(3) << solve() << std::endl;
 
    return 0;
}


就是这样啦~