题意：

给定一个无向有环图（可能有重边），给每一条边编号为 1~m 的不重数值，现在从 1 号节点出发，随机访问相邻节点，得分加上经过的边的编号，到达 n 号节点终止，求通过合理编号，到达 n 号节点时得分期望的最小值。(n<=500)

思路：

1. 对于每一个节点，我们可以通过高斯消元求出它经过次数的期望值。初始时 1 号节点期望为 1，n 号节点期望为 0，列一个方程组就可以求出经过次数的期望值 p[i]。
2. 对于每一条边的期望经过次数，有 $e[i]=\sum{\frac{p[u]}{d[u]}}+\sum{\frac{p[v]}{d[v]}}$其中 u,v 是边 i 的两端点，d[i] 为点 i 的度。
3. 我们需要明确一个事实：对于两个相同长度的序列，其中一个升序排列，当这两个序列排在相同位置的元素的积的和取最小值时，当且仅当另一个序列是降序排列的。
证明：从二元组 (a1,a2),(b1,b2) 着手，如果有 a1<a2,b1<b2, 那么 s1=(a1,a2)(b1,b2)=a1b1+a2b2, 设 s2=(a1,a2)(b2,b1)=a1b2+a2b1,∴s1-s2=a1(b1-b2)+a2(b2-b1)=(b1-b2)(a1-a2)>0,∴a1>a2。我们可以大胆地想，这个结论推广到 n 元组也是适用的。因为两个 n 元组的积一定可以表示为很多个满足上述规律的二元组的积的加减嵌套。
4. 当我们知道了每一条边的经过次数和其编号，答案所有边编号与次数的积的和。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define ldabs(a) (a<0?-a:a)
#define MX 1000

using namespace std;

typedef long double ldb;

ldb mat[MX][MX],ans[MX],eep[MX];
int n,m,fst[MX],nxt[MX*MX],u[MX*MX],v[MX*MX],w[MX*MX],lnum,dnum[MX];

void addeg(int nu,int nv)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum,u[lnum]=nu,v[lnum]=nv;
}

void input()
{
    memset(fst,0xff,sizeof(fst));
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        addeg(a,b);
        dnum[a]++,dnum[b]++;
    }
}

void createmat1()
{
    for(int i=1;i<=n-1;i++)
    {
        for(int j=fst[i];j!=-1;j=nxt[j])
        {
            mat[i][v[j]]+=-(1.0/(ldb)dnum[v[j]]);
            mat[v[j]][i]+=-(1.0/(ldb)dnum[i]);
        }
        mat[i][0]=0;
        mat[i][i]=1;
    }
    mat[1][0]=1;
}

pair<int,int>src[MX*MX];

void gauss()
{
    int mxpos;
    ldb trans,now;
    for(int i=1;i<=n-1;i++)
    {
        mxpos=i;
        for(int j=i;j<=n-1;j++)
            if(ldabs(mat[j][i])>ldabs(mat[mxpos][i]))
                mxpos=j;
        swap(mat[i],mat[mxpos]);
        for(int j=i+1;j<=n-1;j++)
        {
            trans=mat[j][i]/mat[i][i];
            if(ldabs(trans)<0.0000001)continue;
            for(int k=0;k<=n-1;k++)mat[j][k]-=mat[i][k]*trans;
        }
    }
    ans[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        now=mat[i][0];
        for(int j=i+1;j<=n;j++)now-=mat[i][j]*ans[j];
        now/=mat[i][i];
        ans[i]=now;
    }
}

void calcans()
{
    ldb tot=0;
    for(int i=1;i<=lnum;i++)eep[i]=ans[u[i]]/(ldb)dnum[u[i]]+ans[v[i]]/(ldb)dnum[v[i]];
    sort(eep+1,eep+lnum+1);
    for(int i=1;i<=lnum;i++)tot+=eep[i]*(double)(lnum-i+1);
    printf("%.3f\n",(double)tot);
}

int main()
{
    input();
    createmat1();
    gauss();
    calcans();
    return 0;
}