可以将期望用边权 \(w_1,w_2,\cdots,w_n\) 表示，考虑分别求出其系数。
当然，直接算的话复杂度会寄。
考虑将边的期望放到点上。\(E(u,v)=\dfrac{E(u)}{d_u}+\dfrac{E(v)}{d_v}\)
其中 \(E(u)\) 表示经过 \(u\) 点出边次数的期望。
有
\[E(u)=\begin{cases} 0 & u=n \\ 1+\sum\limits_{(u,v)\in E} \dfrac{E(v)}{d_v} &u=1\\ \sum\limits_{(u,v)\in E} \dfrac{E(v)}{d_v} & \operatorname{Otherwise} \end{cases} \]列出方程，大力高消。
算出系数后一个贪心就没了。
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
const int N=505,M=N*N;
int du[N];
struct edge{int u,v;}e[M];
double x[N][N+1];
double w[M];
double p[N];
int main(){
int n,m;io>>n>>m;
for(int i=1;i<=m;++i){
io>>e[i].u>>e[i].v;
++du[e[i].u];++du[e[i].v];
}
for(int i=1;i<=n;++i) x[i][i]=1;
for(int i=1;i<=m;++i){
x[e[i].u][e[i].v]-=1.0/du[e[i].v];
x[e[i].v][e[i].u]-=1.0/du[e[i].u];
}
for(int i=1;i<n;++i) x[n][i]=0;
x[1][n+1]=1;
for(int i=1;i<=n;++i){
int p=i;
for(int j=i+1;j<=n;++j) if(fabs(x[j][i])>fabs(x[p][i])) p=j;
for(int j=1;j<=n+1;++j) swap(x[i][j],x[p][j]);
for(int j=1;j<=n;++j){
if(j==i) continue;
double tmp=x[j][i]/x[i][i];
for(int k=1;k<=n+1;++k) x[j][k]-=tmp*x[i][k];
}
}
for(int i=1;i<=n;++i) p[i]=x[i][n+1]/x[i][i];
for(int i=1;i<=m;++i){
w[i]=p[e[i].u]/du[e[i].u]+p[e[i].v]/du[e[i].v];
}
sort(w+1,w+m+1,[](double a,double b){return a>b;});
double ans=0;
for(int i=1;i<=m;++i){
ans=(ans+i*w[i]);
}
printf("%.3lf\n",ans);
return 0;
}