Description
一个无向连通图，顶点从1编号到N，边从1编号到M。
小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。Input
第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。
Output
仅包含一个实数，表示最小的期望值，保留3位小数。
Sample Input
3 3 2 3 1 2 1 3
Sample Output
3.333
HINT
边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。
Source
数学问题 数学期望 高斯消元+贪心
使得总分期望值最小，显然需要求出每条边的期望被经过次数，然后给次数最多的边标上最小的编号。
一条边(x,y)的期望被经过次数等于点x的经过次数*从x到y的概率(1/出度) +点y的经过次数*从y到x的概率
那么现在只需要求每个点的经过次数就可以了
$P[x]=\sum_{i=1,i!=x}^{n}P[i]*k[i][x]$ $k[i][x]=1.0/outdeg[i]$
特别地，P[1]等于那一串再加一个1，因为点1一开始就被经过了一次
第n个点进去就出不来，可以忽视
↑忽视不代表可以直接删掉第n行第n列，因为其他向量的计算还要用到这部分。
第57、58行算出度，调用了先前的u和v，WAWAWA
1 /*by SilverN*/ 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int mxn=505;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 struct edge{17 int x,y;18 }e[mxn*mxn];19 int n,m;20 double ans=0;21 double f[mxn][mxn];22 void Gauss(){23 int i,j,k;24 for(i=1;i<=n;i++){25 int p=i;26 for(j=i+1;j<=n;j++)if(fabs(f[j][i])>fabs(f[p][i]))p=j;27 if(p!=i)28 for(j=i;j<=n+1;j++)swap(f[p][j],f[i][j]);29 for(j=i+1;j<=n;j++){30 double x=f[j][i]/f[i][i];31 for(k=i;k<=n+1;k++){32 f[j][k]-=f[i][k]*x;33 }34 }35 }36 for(i=n;i;i--){37 for(j=i+1;j<=n;j++)38 f[i][n+1]-=f[i][j]*f[j][n+1];39 f[i][n+1]/=f[i][i]; 40 // printf("i:%.3f\n",f[i][n+1]);41 }42 return;43 }44 double k[mxn][mxn];//点到点转移的概率 45 double g[mxn*mxn];//边被使用的期望次数 46 int out[mxn];//出度47 int cmp(double a,double b){ return a>b;}48 int main(){49 int i,j,u,v;50 n=read();m=read();51 for(i=1;i<=m;i++){52 u=read();v=read();53 e[i].x=u;e[i].y=v;54 ++out[v];++out[u];55 }56 for(i=1;i<=m;i++){57 k[e[i].x][e[i].y]+=(double)1/out[e[i].x];58 k[e[i].y][e[i].x]+=(double)1/out[e[i].y];59 }60 f[1][n+1]=-1;f[n][n]=1;f[n][n+1]=0;61 for(i=1;i