首先想到怎麼求出每一條邊 i i i 在每次遊走中被經過次數的期望 f i f_i fi，那麼答案就可以貪心地取。（即讓最大的 f i f_i fi 權值設為 1 1 1，次大的設為 2 2 2，……，最小的設為 m m m）
但是發現不好統計，或者時間無法承受。
發現點數很小（ n ≤ 500 n\leq 500 n≤500），于是想到怎麼通過點的期望值轉移到邊上。
容易得到：如果設每一個點 u u u 在每次遊走中被經過次數的期望 g u g_u gu，每個點的度數為 d e g u deg_u degu，然後假設某一條邊 i i i 為 ( u , v ) (u,v) (u,v)，那麼有 f i = g u d e g u + g v d e g v f_i=\dfrac{g_u}{deg_u}+\dfrac{g_v}{deg_v} fi=degugu+degvgv。
是以我們隻需要求出 g g g 就可以得到 f f f 了。
容易得到狀态轉移方程：
g u = { 1 + ∑ ( u , v ) g v d e g v u = 1 ∑ ( u , v ) g v d e g v 1 < u < n g_u= \begin{cases} 1+\sum\limits_{(u,v)}\dfrac{g_v}{deg_v}&u=1\\ \sum\limits_{(u,v)}\dfrac{g_v}{deg_v}&1<u<n\\ \end{cases} gu=⎩⎪⎨⎪⎧1+(u,v)∑degvgv(u,v)∑degvgvu=11<u<n
解釋一下：
首先為什麼 u = 1 u=1 u=1 的時候要比其他時候多加 1 1 1，因為初始化的時候本來就應該是 g 1 = 1 g_1=1 g1=1。
然後為什麼 g n g_n gn 不考慮，因為到了 n n n 之後就結束遊走了，不可能再走向下一條邊。
然後這個狀态轉移方程就可以看成是有 n − 1 n-1 n−1 個未知數， n − 1 n-1 n−1 條式子的方程，用高斯消元做就好了。
最後代碼如下：
#include<bits/stdc++.h>
#define N 510
#define M 125010
using namespace std;
int n,m;
int deg[N],from[M],to[M];
double a[N][N],x[N],f[M];
vector<int>e[N];
void Gauss()
{
for(int i=1;i<n;i++)
{
int p=i;
for(int j=i+1;j<n;j++)
if(fabs(a[j][i])>fabs(a[p][i])) p=j;
if(i!=p) swap(a[i],a[p]);
for(int j=i+1;j<n;j++)
{
double tmp=a[j][i]/a[i][i];
for(int k=i;k<=n;k++) a[j][k]-=a[i][k]*tmp;
}
}
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<n;j++) a[i][n]-=x[j]*a[i][j];
x[i]=a[i][n]/a[i][i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from[i],&to[i]);
e[from[i]].push_back(to[i]);
e[to[i]].push_back(from[i]);
deg[from[i]]++,deg[to[i]]++;
}
for(int u=1;u<n;u++)
{
a[u][u]=1;
for(int i=0,size=e[u].size();i<size;i++)
{
int v=e[u][i];
if(v!=n) a[u][v]-=1.0/deg[v];
}
}
a[1][n]=1;
Gauss();
for(int i=1;i<=m;i++)
{
int u=from[i],v=to[i];
if(u!=n) f[i]+=x[u]/deg[u];
if(v!=n) f[i]+=x[v]/deg[v];
}
sort(f+1,f+m+1);
double ans=0;
for(int i=1;i<=m;i++)
ans+=i*f[m-i+1];
printf("%.3lf\n",ans);
return 0;
}