题目描述

一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

输入输出格式

输入格式：

 

第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。

 

输出格式：

 

仅包含一个实数，表示最小的期望值，保留3位小数。

 

输入输出样例

输入样例#1： 

3 32 31 21 3

输出样例#1： 

3.333

说明

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

 

我们发现每条边对答案的贡献就是走这条边的期望(Σ次数*概率)*这条边的编号。

最优方案显然是求出所有期望之后大的期望对应小的编号。。。

但是怎么求边的期望呢？？？

边的期望直接求不好求，可以考虑从点的求得。

设E(x)为走x点的期望(Σ次数*概率)，E(u,v)为走这条边的期望。

那么E(x,y)=E(x)/d(x)+E(y)/d(y)，d(i)表示i点的度数。

当然如果x,y其中一个是n的话就不能算了，因为到了n就结束了，不可能再走这条边。

 

所以现在问题就变成了如何求每个点的期望。

显然E(n)=1,因为n是游戏的终点，最多也最少走一次。

对于其他的x，E(x)=ΣE(v)/d(v) ，条件是存在边(x,v)。

特殊的，对于E(1)，右式还要+1，因为1是起点。

 

这是一个有后效性的方程，我们只能通过高斯消元求解。。。

 

(好像实数高斯消元的精度误差都很毒瘤，，，现在已经很迷茫eps到底取多少了hhhh)

#include
     
      #define ll long long#define D long double#define maxn 505#define maxm 250005using namespace std;const D eps=10e-11;D a[maxn][maxn],tot;D ap[maxm],ans[maxn];int n,m,u[maxm];int v[maxm],d[maxn];bool g[maxn][maxn];inline int zt(D x){    if(x>=-eps&&x<=eps) return 0;    return x>0?1:-1;}inline void solve(){    for(int i=1;i
      
       i;j--) a[i][n]-=ans[j]*a[i][j];        ans[i]=a[i][n]/a[i][i];    }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        scanf("%d%d",u+i,v+i);        d[u[i]]++,d[v[i]]++;        g[u[i]][v[i]]=g[v[i]][u[i]]=1;    }        for(int i=1;i