记录编号	438097	评测结果	AAAAAAAAAA
题目名称	[HNOI 2013]游走	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2017-08-15 13:10:45	内存使用	3.62 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read() {
	int sum(0);
	char ch(getchar());
	for(; ch<'0'||ch>'9'; ch=getchar());
	for(; ch>='0'&&ch<='9'; sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar());
	return sum;
}
struct edge {
	int s,e,n;
} ed[250001];
int pre[501],tot;
inline void insert(int s,int e) {
	ed[++tot].s=s;
	ed[tot].e=e;
	ed[tot].n=pre[s];
	pre[s]=tot;
}
int du[501];
int n,m;
double a[501][501],b[501],ans[501];
inline double jdz(double x) {
	return x>=0?x:-x;
}
inline void swp(double &a,double &b) {
	double c(a);
	a=b;
	b=c;
}
inline void gauss() {
	int num,cnt(1);
	for(int i=1; i<n; ++i,++cnt) {
		num=i;
		for(int j=i+1; j<=n; ++j)
			if(fabs(a[num][i])<fabs(a[j][i]))
				num=j;
		if(num!=i) {
			for(int j=1; j<=n; ++j)
				swap(a[num][j],a[cnt][j]);
			swap(b[num],b[cnt]);
		}
		if(!a[cnt][i]) {
			cnt--;
			continue;
		}
		for(int j=cnt+1; j<=n; ++j) {
			double t(a[j][i]/a[cnt][i]);
			for(int k=i; k<=n; ++k)
				a[j][k]-=t*a[i][k];
			b[j]-=t*b[i];
		}
	}
	for(int i=n; i>0; --i) {
		for(int j=n; j>i; --j)
			b[i]-=a[i][j]*ans[j];
		ans[i]=b[i]/a[i][i];
	}
}
double f[250001];
bool g[501][501];
inline int gg() {
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	n=read(),m=read();
	for(int i=1; i<=m; ++i) {
		int x(read()),y(read());
		insert(x,y);
		g[x][y]=g[y][x]=1;
		du[x]++,du[y]++;
	}
	du[n]=0;
	for(int i=1; i<=n; ++i) {
		if(i==1)
			b[i]=1;
		else
			b[i]=0;
		for(int j=1; j<=n; ++j) {
			if(i==j) {
				a[i][j]=1;
				continue;
			}
			if(j==n) {
				a[i][j]=0;
				continue;
			}
			if(g[i][j])
				a[i][j]=-1.0/(double)du[j];
		}
	}
	gauss();
	for(int i=1; i<n; ++i)
		ans[i]/=du[i];
	ans[n]=0;
	for(int i=1; i<=tot; ++i) {
		int s(ed[i].s),e(ed[i].e);
		f[i]=ans[s]+ans[e];
	}
	int cnt(tot);
	sort(f+1,f+tot+1);
	double an(0);
	for(int i=1; i<=tot; ++i)
		an+=i*f[cnt--];
	printf("%.3lf",an);
	return 0;
}
int k(gg());
int main() {
	;
}