记录编号	577939	评测结果	AAAAAAAAAA
题目名称	[HNOI 2013]游走	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.250 s
提交时间	2022-12-08 22:21:29	内存使用	5.19 MiB

// Problem: #2383. 「HNOI2013」游走
// Contest: LibreOJ
// URL: https://loj.ac/p/2383
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using pii = std::pair<int,int>;
using i64 = long long;

const int maxn = 505;
int n,m,deg[maxn];
std::vector<pii> G[maxn];
double a[maxn][maxn],f[maxn],g[maxn * maxn];

int main() {
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		G[u].pb(v , i);
		G[v].pb(u , i);
		++ deg[u];
		++ deg[v];
	}
	for(int i = 1;i < n;++ i) {
		a[i][i] = 1.0;
		for(auto& [v , id] : G[i]) {
			if(v == n)continue ;
			a[i][v] = -1.0 / (double)deg[v];
		}
	}
	a[1][n] = 1.0;
	for(int i = 1;i < n;++ i) {
		int m = i;
		for(int j = i + 1;j < n;++ j)
			if(std::fabs(a[j][i]) > std::fabs(a[m][i]))
				m = j;
		std::swap(a[i] , a[m]);
		for(int j = 1;j < n;++ j) {
			if(j == i)continue ;
			double d = a[j][i] / a[i][i];
			for(int k = i + 1;k <= n;++ k)
				a[j][k] -= a[i][k] * d;
		}
	}
	for(int i = 1;i < n;++ i)
		f[i] = a[i][n] / a[i][i];
	for(int i = 1;i < n;++ i) {
		for(auto& [v , id] : G[i]) {
			if(v < i)continue ;
			g[id] = f[i] / (1.0 * deg[i]) + f[v] / (1.0 * deg[v]);
		}
	}
	std::sort(g + 1 , g + 1 + m , std::greater<double>());
	double ans = 0;
	for(int i = 1;i <= m;++ i)
		ans += 1.0 * i * g[i];
	printf("%.3lf\n",ans);
	return 0;
}