期望(DP)入门题目。
关键思想：无向边的转移作为有向边考虑。其他的就是直接上全期望公式。由于这个题目不是有向无环图，所以需要高斯消元搞一搞。
设每个点的期望经过次数是(g(x))，那么有
[g(u) = sum_{v} frac{1}{out(v)}*g(v)
]
特殊的，我们认为点(1)有一个一定经过的入边，且不考虑点(n)的所有出边。
这个(g)很好做啊，我们高斯消元搞一搞就好了。那边的期望经过次数(f(x))也就显而易见。
[f(x) = frac{g(u)}{out(u)} + frac{g(v)}{out(v)}
]
然后这个题就做完了。
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 5;
int n, m, u[N * N], v[N * N], out[N];
vector <int> G[N];
double ans, f[N * N], g[N], mat[N][N];
void gauss_jordan () {
for (int i = 1; i <= n; ++i) {
int besti = i;
for (int j = i; j <= n; ++j) {
if (fabs (mat[besti][i]) < fabs(mat[j][i])) {
besti = j;
}
}
if (i != besti) swap (mat[i], mat[besti]);
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
double t = mat[j][i] / mat[i][i];
for (int k = i; k <= n + 1; ++k) {
mat[j][k] -= mat[i][k] * t;
}
}
}
for (int i = 1; i <= n; ++i) {
g[i] = mat[i][n + 1] / mat[i][i];
}
}
int main () {
// freopen ("data.in", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> u[i] >> v[i];
G[u[i]].push_back (v[i]); if (u[i] != n) out[u[i]]++;
G[v[i]].push_back (u[i]); if (v[i] != n) out[v[i]]++;
}
mat[1][n + 1] = 1;
for (int u = 1; u <= n; ++u) {
mat[u][u] = 1;
for (int i = 0; i < G[u].size (); ++i) {
int v = G[u][i];
if (v == n) {
mat[n][v] = -1.0 / out[v];
} else {
mat[u][v] = -1.0 / out[v];
}
}
}
gauss_jordan ();
for (int i = 1; i <= m; ++i) {
if (u[i] != n) f[i] += g[u[i]] / out[u[i]];
if (v[i] != n) f[i] += g[v[i]] / out[v[i]];
}
sort (f + 1, f + 1 + m);
for (int i = 1; i <= m; ++i) {
ans += (m - i + 1) * f[i];
}
cout << fixed << setprecision (3) << ans << endl;
}