根据题意，我们容易发现只要我们得到了每一条边被经过的期望次数就可以给这些边编号。
设 \(d_x\) 表示点 \(x\) 的度数。
所以我们先用高斯消元求出每个点被经过的期望次数 \(f_x\)，那么 $E(u,v) = \frac{f_u}{d_u} + \frac{f_v}{d_v} $。
然后就做完了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e18,N=5e2+5;
int n,m;
int du[N];
struct edge{int u,v;}p[N*N];
double a[N][N],res[N],num[N*N];
vector<int> ed[N];
inline void Guass(int n){
for(int i=1;i<=n;i++){
int now=i;
for(int j=i+1;j<=n;j++) if(fabs(a[now][i])<fabs(a[j][i])) now=j;
for(int j=1;j<=n+1;j++) swap(a[now][j],a[i][j]);
for(int k=n+1;k>=i;k--) for(int j=i+1;j<=n;j++)
a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
}
for(int i=n;i>=1;i--){
res[i]=a[i][n+1]/a[i][i];
for(int j=1;j<i;j++)
a[j][n+1]-=res[i]*a[j][i];
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
p[i]={u,v};
du[u]++,du[v]++;
ed[u].push_back(v);
ed[v].push_back(u);
}
for(int x=1;x<n;x++){
a[x][x]=1;
for(auto v:ed[x]){
if(v!=n)
a[x][v]=(double)-1/du[v];
}
}
a[1][n]=1;
Guass(n-1);
for(int i=1;i<=m;i++){
auto [u,v]=p[i];
if(u!=n) num[i]+=res[u]/du[u];
if(v!=n) num[i]+=res[v]/du[v];
}
sort(num+1,num+m+1);
double ans=0;
for(int i=m;i>=1;i--) ans+=(m-i+1)*num[i];
printf("%.3lf\n",ans);
}