记录编号	467579	评测结果	AAAAAAAAAA
题目名称	[HNOI 2013]游走	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.214 s
提交时间	2017-10-30 20:03:45	内存使用	6.53 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
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
const double eps=1e-10;
int n,m;
struct haha{
	int from,to;
}edge[N*N];
double f[N],a[N][N],b[N],x[N];
bool lian[N][N];
int du[N],flag;
double hswap(double &aa,double &bb){
	double temp=aa;aa=bb;bb=temp;
}
void guess(){
	int num=1;
	for(int k=1;k<n-1;k++,num++){
		int im=k;
		pos(i,k+1,n-1){
			if(fabs(a[i][k])>fabs(a[im][k])) im=i;
		}
		if(im!=k){
			pos(i,k,n-1){
				hswap(a[im][i],a[num][i]);
			}
			hswap(b[im],b[num]);
		}
		if(a[num][k]==0){
			num--;continue;
		}
		pos(i,num+1,n-1){
			double t=a[i][k]/a[num][k];
			pos(j,k,n-1){
				a[i][j]-=t*a[k][j];
			}
			b[i]-=t*b[k];
		}
	}
	pos(i,num,n-1){
		if(a[i][n-1]==0&&b[i]){
			flag=-1;return;
		}
	}
	pos2(i,n-1,1){
		pos2(j,n-1,i+1){
			b[i]-=a[i][j]*x[j];
		}
		if(a[i][i]==0&&b[i]){
			flag=-1;return;
		}
		if(a[i][i]==0&&b[i]==0){
			flag=0;return;
		}
		x[i]=b[i]/a[i][i];
	}
	flag=1;return;
}
struct xixi{
	double num2;
	bool operator <(const xixi &f)const{
		return num2<f.num2;
	}
}bian[N*N];
double ans;
int main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	scanf("%d%d",&n,&m);
	pos(i,1,m){
		int x,y;scanf("%d%d",&x,&y);
		edge[i].from=x;edge[i].to=y;
		lian[x][y]=lian[y][x]=1;
		du[x]+=1.0;du[y]+=1.0;
	}
	pos(i,1,n-1){
		a[i][i]=-1.0;
		pos(j,1,n-1){
			if(lian[i][j]){
				a[i][j]=1.0/du[j];
			}
		}
	}
	x[n]=1;
	b[1]=-1.0;
	guess();
//	pos(i,1,n) cout<<"x[i]="<<x[i]<<endl;
	du[n]=0;
	pos(i,1,m){
		if(du[edge[i].to]!=0&&du[edge[i].from]!=0){
			bian[i].num2=x[edge[i].from]/du[edge[i].from]+x[edge[i].to]/du[edge[i].to];
		}
		else{
			if(du[edge[i].from]!=0){
				bian[i].num2=x[edge[i].from]/du[edge[i].from];
			}
			else bian[i].num2=x[edge[i].to]/du[edge[i].to];
		}	
	}
	sort(bian+1,bian+m+1);
	pos(i,1,m){
		//cout<<bian[i].num2<<endl;
		ans+=(m-i+1)*bian[i].num2;
	}
	//cout<<bian[510].num2;
	printf("%.3lf",ans);
	return 0;
}