题解

记 $f_u$ 为从点 $u$ 出发一直走到 $N$ 号点的过程中所获得分数的期望。对于终点 $f_N = 0$，而对于其它点有

$$f_u = \frac{1}{\deg(u)} \sum_{(u,v)\in E} (w_{uv} + f_v), $$

其中 $w_{uv}$ 是边的编号。由于边的编号未知，我们只需要先求出“期望经过每条边的次数”，把编号大的边放在期望次数小的位置即可。

进一步化简可得线性方程组：把式子移项，得到

$$f_u - \sum_{v\neq N} \frac{1}{\deg(v)} f_v = \begin{cases} 1, & u = 1, \\ 0, & u \neq 1, N. \end{cases} $$

这正好是一个 $(N-1)$ 阶的高斯消元方程，可以解出所有 $f_u$。对于一条边 $(x,y)$，它被经过的期望次数等于从两端出发的转移概率之和，即

$$g_{xy} = \frac{f_x}{\deg(x)} + \frac{f_y}{\deg(y)} $$

（若其中一端是终点，则只有另一端的项）。

把所有边的 $g_i$ 按升序排序之后，依次分配编号 $1..M$，这样对每条边的贡献就是 $g_i \times$ 对应编号。由于我们希望总期望最小，应该把大的编号分给较小的 $g_i$，因此最终答案即为

$$\sum g_i \cdot (M - i + 1).$$

实现时用高斯消元解线性方程，再排序即可输出保留三位小数的期望。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=125010;
int n,m,out[N],u[M],v[M];
vector<int>t[N];
double ans=0,a[N][N],g[M];
void guess(int n){
	for(int i=1;i<=n;i++){
		int maxn=i;
		for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[maxn][i])) maxn=j;
		for(int j=1;j<=n+1;j++) swap(a[maxn][j],a[i][j]);
		for(int j=n+1;j>=i;j--) a[i][j]=a[i][j]/a[i][i];
		for(int j=1;j<=n;j++){
			if(j!=i){
				double temp=a[j][i]/a[i][i];
				for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*temp;
			}
		}
	}
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		if(x==n) swap(x,y);
		u[i]=x,v[i]=y;
		t[x].push_back(y);t[y].push_back(x);
		out[x]++;out[y]++;
	}
	a[1][n]=1.0;
	for(int i=1;i<n;i++){
		a[i][i]=1.0;
		for(int j:t[i]){
			if(j!=n) a[i][j]=-1.0/out[j];
		}
	}
	guess(n-1);
	for(int i=1;i<=m;i++){
		if(v[i]==n) g[i]=a[u[i]][n]*1.0/out[u[i]];
		else g[i]=a[u[i]][n]*1.0/out[u[i]]+a[v[i]][n]*1.0/out[v[i]];
	}
	sort(g+1,g+1+m);
	for(int i=1;i<=m;i++) ans+=g[i]*1.0*(m-i+1);
	cout<<fixed<<setprecision(3)<<ans;
}