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 DEFINESstruct my_stream {int x;operator int() {scanf("%d", &x);return x;}
} __rp_read;
#define input() __rp_readconst 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;
}