一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。
做过一道类似的后感觉比较简单了
求$f[i]$到每个点的概率
$f[i]=\sum\limits_{(i,j) \in E}{f[j]*\frac{1}{d[j]}}$
$f[1]$额外加上$1$
$f[n]=0$因为到$n$后就不走了没必要用$n$的概率
然后就可以得到通过一条边的概率啦，贪心分配即可
然后BZOJ数据太弱了....洛谷的数据在消元时还要判断系数$<eps$
PS:这种题应该保证有解吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=;
double eps=1e-;
inline int read(){
char c=getchar();int x=;
while(c<''||c>''){c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n,m,u,v;
int d[N];
double p[N],a[N][N];
struct edge{
int v,ne,u;
}e[N*N<<];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].u=v;e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
void buildEquation(){
for(int i=;i<n;i++){
a[i][i]=;int j;
for(int k=h[i];k;k=e[k].ne) j=e[k].v,a[i][j]=-1.0/d[j];
}
a[][n+]=;
a[n][n]=;a[n][n+]=;
}
void GaussElimination(){
for(int i=;i<=n;i++){
int r=i;
for(int j=i+;j<=n;j++) if(abs(a[j][i])>abs(a[r][i])) r=j;
if(r!=i) for(int k=;k<=n+;k++) swap(a[r][k],a[i][k]);
for(int j=i+;j<=n;j++) if(abs(a[j][i])>eps){
double t=a[j][i]/a[i][i];
for(int k=i;k<=n+;k++) a[j][k]-=t*a[i][k];
}
}
for(int i=n;i>=;i--){
for(int j=n;j>i;j--) a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
p[i]=a[i][n+];
}
}
double f[N*N];
void solve(){
for(int i=;i<=m;i++){
int u=e[i<<].u,v=e[i<<].v;
f[i]=p[u]/d[u]+p[v]/d[v];
}
sort(f+,f++m);
double ans=;
for(int i=;i<=m;i++) ans+=(m-i+)*f[i];
printf("%.3lf",ans);
}
int main(){
freopen("in","r",stdin);
n=read();m=read();
for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v),d[u]++,d[v]++;
buildEquation();
GaussElimination();
solve();
}