原題：

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;
}