纪念首道期望题（虽说绿豆蛙的归宿才是，但是我打的深搜总觉得不正规）。
我们求出每条边的期望经过次数，然后排序，经过多的序号小，经过少的序号大，这样就可以保证最后的值最小。
对于每一条边的期望经过次数，其实是从它起点和终点来的。设f[]为每个点经过的期望,out[]为每个点的出度
设一条边，起点为u，终点为v。那么它的期望经过次数为f[u]/out[u]+f[v]/out[v]
这样问题就转化为求每个点的期望经过次数了
对于起点,一开始经过一次,也可能从其他点走过来.
f[1]=1+sigma(f[j]/out(j),j和1有边)
f[i]=sigma(f[j]/out(j),j和i有边) //i>=2
这是n个变量n个方程的方程组,高斯消元解方程组,O(n^3)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 510
int n,m;
int read()
{
int su=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch<='9'&&ch>='0'){
su=su*10+ch-'0';ch=getchar();
}
return su;
}
double out[N];
double a[N][N],b[N],x[N];
int lian[N][N];
void swap(double &xx,double &yy)
{
double temp;
temp=xx;
xx=yy;
yy=temp;
}
void gauss(){
double t;
int im,num=1;
for(int k=1;k<n;k++,num++) {
im=k;
pos(i,k+1,n)
if(fabs(a[i][k])>fabs(a[im][k]))
im=i;
if(im!=k){
pos(i,k,n)
swap(a[num][i],a[im][i]);
swap(b[num],b[im]);
}
if(!a[num][k]){
num--;
continue;
}
pos(i,num+1,n){
if(!a[num][k])
continue;
t=a[i][k]/a[num][k];
pos(j,k,n+1)
a[i][j]-=t*a[k][j];
b[i]-=t*b[k];
}
}
pos2(i,n,1){
pos2(j,n,i+1)
b[i]-=a[i][j]*x[j];
x[i]=b[i]/a[i][i];
}
}
struct qian{
int from,to;
double e;
}cun[N*N];
bool aaa(const qian &a,const qian &b){
return a.e<b.e;
}
double ans;
int messi(){
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
n=read();m=read();
pos(i,1,m){
int x,y;
x=read();y=read();
lian[x][y]=lian[y][x]=1;
out[x]+=1.0;out[y]+=1.0;
cun[i].from=x;cun[i].to=y;
}
out[n]=0.0;
a[1][1]=-1.0;
b[1]=-1.0;
pos(i,2,n){
if(lian[i][1]==1&&out[i]){
a[1][i]=1.0/out[i];
}
}
pos(i,2,n){
a[i][i]=-1.0;
pos(j,1,n){
if(j!=i&&lian[j][i]==1&&out[j]){
a[i][j]=1.0/out[j];
}
}
}
gauss();
pos(i,1,m){
if(out[cun[i].from]!=0&&out[cun[i].to]!=0)
cun[i].e=x[cun[i].from]/out[cun[i].from]+x[cun[i].to]/out[cun[i].to];
else{
if(out[cun[i].from]==0)
cun[i].e=x[cun[i].to]/out[cun[i].to];
else
cun[i].e=x[cun[i].from]/out[cun[i].from];
}
}
sort(cun+1,cun+m+1,aaa);
pos(i,1,m){
ans+=cun[i].e*(double)(m-i+1);
}
printf("%0.3lf",ans);
return 0;
}
int hallmeow=messi();
int main(){;}