\textbf{7.26 T2}
\textbf{Description}
一个人在该图上进行随机游走，初始时他在 1 号节点，每一步会以等概率随机选择一条相邻的边，沿着这条边走到下一个节点，并获得经过边的权。
在到达 n 号节点后游走结束，总分为获得的边权和。现在，对着 m 条边编号，使得他获得的总分期望最小。
1\le n \le 250,1\le m\le 125000 。
原题 [HNOI2013] 游走 中的编号在这里换成了边权，我认为题目描述这样更自然。
\textbf{Sol.}
边权？那玩意是啥？看到边什么的果断转成点！
设 E(u) 为点 u 的经过次数的期望。对于所有 $(u,v)\in E$，结点 v 都有 (1/\text{deg}(v)) 的概率在下一步选择 $u$。因此：
E(u)=\sum_{(u,v)\in E}\dfrac {E(v)}{\text{deg}(v)}
需要注意的是，条件 (u,v)\in E 并不完全对。点 v 对点 u 有贡献，当且仅当点 v 在下一步有概率选择 $u$。所以会有特殊情况：
对于 1 号结点，除了其他点转移而来的贡献，初始以 1 为结点这一条件已经为 E(1) 带来了 1 的贡献。
对于 n 号结点，它不能由任何点转移而来，所以 E(n)\equiv 0 。
于是你得到了一个 (n-1) 元线性方程组（ E(n)=1 ，可以直接忽略），高斯消元可以解得所有点经过次数的期望。
那么点的问题就搞定了，现在来看看怎么重新转化为边。你当然可以 dfs 下传点权，但是我懒得搞。
边连接的是两个点，因此对于 e=(u,v)(u\ge n, v\ge n) ，它的期望经过次数 E^{'}(e) 可以通过 E(u) 和 E(v) 表示。
E^{'}(e)=\dfrac{E(u)}{\text{deg}(u)}+\dfrac{E(v)}{\text{deg}(v)}
总分的期望就是：
\sum_{e\in E}w(e)\times E^{'}(e)
由排序不等式可知，大的点权应当与期望经过次数小的值相乘。直接 std::sort 就完事了。
为什么我要浪费篇幅来讲这个？因为我觉得排序不等式的证明很好玩（调整法），大家有兴趣可以 bdfs。
\textbf{AC Code}
#include <bits/stdc++.h>
typedef long long i64;
constexpr int N = 505;
constexpr int M = 125005;
constexpr double eps = 1e-10;
int s[M], t[M], deg[N];
struct Edge { int to, nxt; } E[M << 1];
int head[N], tot;
inline void addEdge(int u, int v) {
E[++tot] = Edge{v, head[u]}, head[u] = tot;
}
long double a[N][N], f[M], ans = 0;
inline void Gauss(int n) {
for(int i = 1; i <= n; i++) {
int pos = i;
for(int j = i + 1; j <= n; j++) {
if(a[j][i] > a[pos][i]) {
pos = j;
}
}
for(int j = 1; j <= n + 1; j++) {
std::swap(a[i][j], a[pos][j]);
}
if(fabs(a[i][i]) < eps) continue;
for(int j = i + 1; j <= n + 1; j++) a[i][j] /= a[i][i];
a[i][i] = 1;
for(int j = 1; j <= n; j++) {
if(i == j) continue;
for(int k = i + 1; k <= n + 1; k++) {
a[j][k] -= a[j][i] * a[i][k];
}
a[j][i] = 0;
}
}
}
int n, m;
signed main() {
std::cin.tie(nullptr) -> sync_with_stdio(false);
std::cin >> n >> m;
for(int i = 1; i <= m; i++) {
std::cin >> s[i] >> t[i];
addEdge(s[i], t[i]), deg[s[i]]++;
addEdge(t[i], s[i]), deg[t[i]]++;
}
for(int u = 1; u < n; u++) {
a[u][u] = 1;
for(int i = head[u], v; i; i = E[i].nxt) {
if((v = E[i].to) ^ n) a[u][v] = -1.0 / deg[v];
}
}
a[1][n] = 1;
Gauss(n - 1);
for(int i = 1; i <= m; i++) {
int u = s[i], v = t[i];
f[i] = a[u][n] / deg[u] + a[v][n] / deg[v];
}
std::sort(f + 1, f + m + 1);
for(int i = 1; i <= m; i++) {
ans += f[i] * (m - i + 1);
}
std::cout << std::fixed << std::setprecision(3);
std::cout << ans << '\n';
return 0;
}