P3232 [HNOI2013] 游走，solution

原题：

link，点击这里喵。

题意：

给定一个 $n$ 个点 $m$ 条边的无向连通图，图无重边和自环，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

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

$n\le 500$。

解法

这种乱动就很烦，考虑通过列出方程式解答。

设 $f_i$ 为第个 $i$ 点期望到达的次数，我们有：
$$f_u=(\sum _{v\in ou{t}_u\&v\ne n}\frac{f_v}{d_v})+[u=1]$$
高斯消元即可。

然后就见了。

代码 time ~

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

#define inf 0x3f3f3f3f
typedef long long lnt;

namespace DEFINES {
// #define TEST
// #define Debug
#ifdef Debug
#define dprintf(a, ...) printf(a, ##__VA_ARGS__)
#else
#define dprintf(a, ...)
#endif
} // namespace DEFINES

struct my_stream {
    int x;
    operator int() {
        scanf("%d", &x);
        return x;
    }
} __rp_read;
#define input() __rp_read

const int N = 300 + 20;

double v[N][N]; // data of equations

// 约定：
// x 从 1 开始编号
// v[i][n + 1] 存储常数项

vector<int> G[N];
int n, m, d[N];
double inv_d[N];

struct Edge {
    int x, y;
} edge[N * N];

void init_equations() {           //
    v[1][n + 1] = 1;              // 哇嗷
    for (int i = 1; i < n; ++i) { // 注意是 < 号，不能从 n 点获得转移！
        inv_d[i] = 1.0 / d[i];
    }
    for (int i = 1; i <= n; ++i) { //
        v[i][i] = -1;
        for (const int &e : G[i]) {
            v[i][e] = inv_d[e];
        }
    }
}

void sc() {
    putchar(10);
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= n + 1; ++k) {
            printf("%8.3lf", v[i][k]);
        }
        putchar(10);
    }
    putchar(10);
}

void solve() {                         //
    for (int i = 1; i <= n - 1; ++i) { // 这一项包有值的，省去一步
        for (int e = i + 1; e <= n; ++e) {
            double r = v[e][i] / v[i][i];
            for (int k = i; k <= n + 1; ++k) {
                v[e][k] -= r * v[i][k];
            }
        }
        // sc();
    }
    // sc();
    for (int i = 1; i <= n; ++i) v[i][n + 1] *= -1;
    for (int i = n; i >= 1; --i) {
        v[i][n + 1] /= v[i][i];
        v[i][i] = 1;
        for (int e = i - 1; e >= 1; --e) {
            v[e][n + 1] -= v[e][i] * v[i][n + 1];
            v[e][i] = 0;
        }
    }
}

double _edge[N * N], _v[N];

int main() { //
    n = input(), m = input();
    for (int i = 0; i < m; ++i) {
        int x = input(), y = input();
        edge[i] = {x, y};
        ++d[x], ++d[y];
        G[x].push_back(y);
        G[y].push_back(x);
    }
    init_equations();
    // sc();
    solve();
    // sc();
    for (int i = 1; i < n; ++i) { // 是 < 
        _v[i] = v[i][n + 1] / d[i];
        dprintf("%.3lf\n",_v[i]);
    }
    for (int i = 0; i < m; ++i) {
        _edge[i] = _v[edge[i].x] + _v[edge[i].y];
    }
    sort(_edge, _edge + m, greater<double>());
    double ans = 0;
    for (int i = 0; i < m; ++i) {
        ans += _edge[i] * (i + 1);
        dprintf("%.3lf\n",_edge[i]);
    }
    printf("%.3lf",ans);
    return 0;
}