传送门

我要被「冰菓」的狗粮甜死了。。。

设$f(i)$为期望经过点$i$的次数。

显然，$f(i)=\sum\limits_{edge(i,v)}\dfrac{f(v)}{d(v)}$，$d(v)$为点$v$的度数。

由于是无向连通图，没法直接$DP$，得用高斯消元解出来。（吓得我又重背学了遍高消）

还有俩特殊点：$1$和$n$。点$1$为起点，$f(1)$要$+1$；点$n$为终点，列方程时不要管点$n$，只解出前$n-1$个点。

设$g(i)$为期望经过边$i$的次数。

经过边$i$是从两个端点过来的，于是$g(i)=\dfrac{x_i}{d(x_i)}+\dfrac{y_i}{d(y_i)}$

因为不会从点$n$走过来，所以$x_i,y_i\neq n$。

最后排个序贪心标号即可。

代码：

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

#define maxn 505
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
double a[maxn][maxn],f[maxn],g[maxn*maxn];
int n,d[maxn],x[maxn*maxn],y[maxn*maxn];
vector<int>e[maxn];
void Gauss(){
    for(register int i=1;i<n;++i){
        int now=i;
        for(register int j=i+1;j<n;++j)
            if(fabs(a[now][i])<fabs(a[j][i]))now=j;
        if(i!=now)for(register int j=i;j<=n;++j)swap(a[now][j],a[i][j]);
        double main=a[i][i];
        for(register int j=i;j<=n;++j)a[i][j]/=main;
        for(register int j=i+1;j<n;++j){
            double p=a[j][i];
            for(register int k=i;k<=n;++k)
                a[j][k]-=p*a[i][k];
        }
    }
    for(register int i=n-1;i;--i){
        f[i]=a[i][n];
        for(register int j=i+1;j<n;++j)
            f[i]-=a[i][j]*f[j];
    }
}
int main(){
    n=read();
    int m=read();
    double ans=0.0;
    for(register int i=1;i<=m;++i){
        ++d[x[i]=read()],++d[y[i]=read()];
        e[x[i]].push_back(y[i]),e[y[i]].push_back(x[i]);
    }
    for(register int i=1;i<n;++i){
        for(vector<int>::iterator iter=e[i].begin();iter!=e[i].end();++iter)
            if(*iter!=n)a[i][*iter]=-1.0/(1.0*d[*iter]);
        a[i][i]=1.0;
    }
    a[1][n]=1.0;
    Gauss();
    for(register int i=1;i<=m;++i){
        if(x[i]!=n)g[i]=f[x[i]]/(double)d[x[i]];
        if(y[i]!=n)g[i]+=f[y[i]]/(double)d[y[i]];
    }
    sort(g+1,g+1+m);
    for(register int i=1;i<=m;++i)
        ans+=g[i]*(double)(m-i+1);
    printf("%.3lf\n",ans);
}