[HNOI2013]游走题解

题目链接

题意

给你一个\(n\)个点\(m\)条边的无向连通图从 1 号点出发，每次随机选择当前顶点的某条边走到下一个点，并获得这条边的分数，分数为这条边的编号，一旦到了\(n\)号点就结束游走，总分为获得分数的总和。安排每条边的编号，使总分的期望值最小，并输出最小的期望值

题解

看完题目能够发现，我们只要求出经过每一条边的期望，再把小的编号安排到期望值大的边上，把大的编号安排到期望值小的边上，就可以使总分的期望值最小

分析一波，发现边的期望值并不好求，但是可以先求出点的期望值

显然,每个点的期望是由相连的点的期望决定的。设\(f[x]\)为点\(x\)的期望， \(du[x]\)为点\(x\)的度数,点\(x1,x2,x3....xk\)与点\(x\)相邻，则\(f[x]= \sum_{i=1}^k \frac {f[x_i]}{du[x_i]}\)

这样，点的期望值就转化为了一个方程组，这个时候就要用到我们的高斯消元了，不过要注意的是，因为到了点\(n\)就会停止游走，所以点\(n\)的期望是不用管的。还有，因为起点为1号点，所以点1的实际期望为原期望+1

接下来要做的就是把点的期望转化为边的期望，每条边的期望都由其连接的两个端点决定，最后排个序，安排一下编号即可

最后上代码

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double a[503][503], b[503], f[503], chu, ff[1000000], sum, du[503];
int n, m, max1, x, y, bian[1000000], bian1[1000000];
vector<int> l[503];
signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        l[x].push_back(y), l[y].push_back(x), du[x]++, du[y]++, bian[i] = x, bian1[i] = y;
    }
    b[1] = 1;
    for (int i = 1; i < n; i++) {
        a[i][i] = 1.0;
        for (int j = 0; j < l[i].size(); j++)
            if (l[i][j] != n)
                a[i][l[i][j]] += -1.0 / (double)du[l[i][j]];
    }
    for (int i = 1; i < n; i++) {
        max1 = i;
        for (int j = i + 1; j < n; j++)
            if (a[j][i] > a[max1][i])
                max1 = j;
        if (i != max1)
            swap(a[i], a[max1]), swap(b[i], b[max1]);
        for (int j = i + 1; j < n; j++) {
            chu = a[j][i] / a[i][i], b[j] -= b[i] * chu;
            for (int k = i; k < n; k++) a[j][k] -= a[i][k] * chu;
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        f[i] = b[i] / a[i][i];
        for (int j = 1; j < i; j++) b[j] -= a[j][i] * f[i];
    }
    for (int i = 1; i <= m; i++)
        ff[i] = f[bian[i]] / (double)du[bian[i]] + f[bian1[i]] / (double)du[bian1[i]];
    sort(ff + 1, ff + m + 1);
    for (int i = 1; i <= m; i++) sum += ff[i] * (double)(m - i + 1);
    printf("%.3lf", sum);
    return 0;
}