题目地址：洛谷：【P3232】[HNOI2013]游走 – 洛谷、BZOJ：Problem 3143. — [Hnoi2013]游走

题目描述

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

输入输出格式

输入格式：
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。
输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。

输出格式：
仅包含一个实数，表示最小的期望值，保留3位小数。

输入输出样例

输入样例#1：

3 3
2 3
1 2
1 3

输出样例#1：

3.333

说明

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

题解

显然，如果我们知道经过每一条边的期望经过次数，那么贪心地按期望从大到小安排编号就好了。考虑如何求经过边的期望，边$(u, v)$的期望$\mathrm{E}(u, v)$是
$$ \mathrm{E}(u, v) = \frac{\mathrm{E}(u)}{deg_u} + \frac{\mathrm{E}(v)}{deg_v} $$
其中$deg_u$表示$u$的度数。我们把问题转化成如何求经过$u$点的期望$\mathrm{E}(u)$了。
这里我们考虑使用高斯消元解方程组的思路求解，对于每一个点，可以列出如下方程
$$ \mathrm{E}(u) = \sum_{(u, v) \in G, v \neq n} \frac{\mathrm{E}(v)}{deg_v} $$
移项后即可得到适合高斯消元的式子。对于$1$点，令高消方程的等号右边为$1$即可，这是让$1$强制至少经过1次。
复杂度$O(n^3)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>
#include <vector>
#include <functional>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    register char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 505;

int n, m, deg[MAXN];
double mat[MAXN][MAXN];

inline void gauss() {
    for(int i = 1; i < n; i++) {
        int k = i;
        for(int j = i + 1; j < n; j++) {
            if(fabs(mat[k][i]) < fabs(mat[j][i])) k = j;
        }
        if(k != i) {
            for(int j = 1; j < n + 1; j++) {
                std::swap(mat[k][j], mat[i][j]);
            }
        }
        for(int j = 1; j < n; j++) {
            if(j == i) continue;
            double r = mat[j][i] / mat[i][i];
            for(int k = 1; k < n + 1; k++) {
                mat[j][k] -= r * mat[i][k];
            }
        }
    }
    for(int i = 1; i < n; i++) mat[i][n] /= mat[i][i];
}

std::vector<int> gra[MAXN];

struct Edge {
    int u, v;
    double prob;
    inline bool operator>(const Edge &rhs) const {
        return prob > rhs.prob;
    }
} edges[MAXN * MAXN];

int main() {
    n = readint(); m = readint();
    for(int i = 1, u, v; i <= m; i++) {
        u = readint(); v = readint();
        deg[u]++; deg[v]++;
        edges[i] = Edge {u, v};
        gra[u].push_back(v); gra[v].push_back(u);
    }
    for(int i = 1; i < n; i++) {
        mat[i][i] = 1;
        for(int j = 0; j < gra[i].size(); j++) {
            int v = gra[i][j];
            if(v == n) continue;
            mat[i][v] = -1.0 / deg[v];
        }
    }
    mat[1][n] = 1;
    gauss();
    for(int i = 1; i <= m; i++) {
        edges[i].prob = mat[edges[i].u][n] / deg[edges[i].u] + mat[edges[i].v][n] / deg[edges[i].v];
    }
    std::sort(edges + 1, edges + m + 1, std::greater<Edge>());
    double ans = 0;
    for(int i = 1; i <= m; i++) {
        ans += i * edges[i].prob;
    }
    printf("%.3lf", ans);
    return 0;
}