记录编号	425523	评测结果	AAAAAAAAAA
题目名称	2477.[HNOI 2013]游走	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.190 s
提交时间	2017-07-15 11:55:14	内存使用	3.63 MiB

#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,n){
		cout<<"x[i]="<<x[i]<<endl;
	}*/
	pos(i,1,m){
		//cout<<"from="<<cun[i].from<<"   to="<<cun[i].to<<"   x[from]="<<x[cun[i].from]<<"   x[to]="<<x[cun[i].to]<<"   out[from]="<<out[cun[i].from]<<"  out[to]="<<out[cun[i].to]<<endl;
		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];
		}
		//cout<<cun[i].e<<endl;
	}
	sort(cun+1,cun+m+1,aaa);
	pos(i,1,m){
		ans+=cun[i].e*(double)(m-i+1);
	}
	printf("%0.3lf",ans);
	//while(1);
	return 0;
}
int hallmeow=messi();
int main(){
	;
}