题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=3143
题解：
期望dp，高斯消元
首先有这样一种贪心分配边的编号的方案：（然后我没想到，233）
我们按每一条边的期望经过次数去分配编号，
具体来说，就是期望经过次数越多的边，分配的编号越小，反之则编号越大。
然后问题转化为如何求一条边的期望经过次数。(把求边的期望转化为求点的期望)
我们定义cnt[i]表示i点的出度，dp[i]表示期望经过i点的次数。
然后对于一个边(u,v)，期望经过该边的次数为dp[u]/cnt[u]+dp[v]/cnt[v].
特别的：当u或者v为N号点时，对边的期望贡献为0，因为到了N点就结束了。
所以现在需要求出dp[i].
由全期望公式$$dp[i]=sum_{j->i}dp[j]/cnt[j]$$
特别的：
1.j!=N，因为到达N点就已经结束游戏。
2.当i==1时，dp[i]还要多加一个数值1,因为初始是就期望直接经过了1次。
显然这个DP存在环，所以高斯消元解出dp值，然后再求出每一条边的期望经过次数，贪心地去编号即可。
注：高斯消元判断系数是否为0时,要用到eps，否则可能因为精度问题而出错。
代码：
#include<bits/stdc++.h>
#define MAXN 505
using namespace std;
const double eps=1e-7;
struct EDGE{
int u,v; double exp;
bool operator < (const EDGE &rtm) const{
return exp>rtm.exp;
}
}E[MAXN*MAXN];
double a[MAXN][MAXN],dp[MAXN],ans;
double *A[MAXN];
bool Edge[MAXN][MAXN];
int cnt[MAXN];
int N,M;
int dcmp(double x){
if(fabs(x)<=eps) return 0;
return x>0?1:-1;
}
void Gausselimination(int pos,int i){
if(pos==N+1||i==N+1) return;
for(int j=pos;j<=N;j++) if(dcmp(A[j][i])!=0){
swap(A[pos],A[j]); break;
}
if(dcmp(A[pos][i])!=0){
for(int j=pos+1;j<=N;j++){
double k=A[j][i]/A[pos][i];
for(int l=i;l<=N+1;l++)
A[j][l]-=A[pos][l]*k;
}
}
Gausselimination(pos+(dcmp(A[pos][i])!=0),i+1);
if(dcmp(A[pos][i])!=0){
for(int l=i+1;l<=N;l++)
dp[i]+=A[pos][l]*dp[l];
dp[i]=A[pos][N+1]-dp[i];
dp[i]=dp[i]/A[pos][i];
}
}
void buildequation(){
for(int i=1;i<=N;i++){
a[i][i]=-1;
if(i==1) a[i][N+1]=-1;
for(int j=1;j<N;j++){
if(!Edge[j][i]) continue;
a[i][j]=1.0/cnt[j];
}
}
for(int i=1;i<=N;i++) A[i]=a[i];
}
int main(){
scanf("%d%d",&N,&M);
for(int i=1,u,v;i<=M;i++){
scanf("%d%d",&u,&v);
E[i].u=u; E[i].v=v;
Edge[u][v]=Edge[v][u]=1;
cnt[u]++; cnt[v]++;
}
buildequation();
Gausselimination(1,1);
for(int i=1,u,v;i<=M;i++){
u=E[i].u; v=E[i].v;
E[i].exp=(u!=N?dp[u]/cnt[u]:0)+(v!=N?dp[v]/cnt[v]:0);
}
sort(E+1,E+M+1);
for(int i=1;i<=M;i++)
ans+=E[i].exp*i;
printf("%.3lf
",ans);
return 0;
}