嘟嘟嘟
[数组越界真刺激，debug到怀疑人生]
我们可以求出每一条边的期望，然后贪心的把期望大的赋上小边权。
而对于边(e<x, y>)的期望(E(e) = frac{E(x)}{du[x]} + frac{E(y)}{du[y]})。(du[x])表示(x)有几条出边。
理解起来就是这条边的期望等于两端点期望的并相加。
所以现在转化成了求每一个点的期望。
容易列出：(E(x) = sum _ {v in V} frac{E(v)}{du[v]})，((V)表示(x)的出边集合)。
其中(E(1) = 1 + sum _ {v in V} frac{E(v)}{du[v]})
因为刚开始在1，至少经过一次。
然而这东西不能dp，因为不满足后效性。
但是咧，仔细观察一下，发现如果把每一个点的式子看成一个多元方程，那么所有的就构成了一个多元线性方程组。于是高斯消元就派上用场了。
需要注意的是，因为走到(n)就停，所以求期望的时候不能算上(n)的贡献。那么也就说明这个增广矩阵是((n - 1) * n)的。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 505;
const int maxe = 1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, du[maxn];
struct Edge
{
int nxt, to;
}e[maxe];
int head[maxn], ecnt = -1;
void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
struct Node
{
int x, y; db w;
bool operator < (const Node& oth)const
{
return w > oth.w;
}
}t[maxe];
db f[maxn][maxn], ans[maxn];
int main()
{
Mem(head, -1);
n = read(); m = read();
for(int i = 1; i <= m; ++i)
{
t[i].x = read(); t[i].y = read();
addEdge(t[i].x, t[i].y); addEdge(t[i].y, t[i].x);
du[t[i].x]++; du[t[i].y]++;
}
f[1][n] = -1;
for(int i = 1; i < n; ++i)
{
f[i][i] = -1;
for(int j = head[i]; j != -1; j = e[j].nxt)
if(e[j].to != n) f[i][e[j].to] = 1.0 / du[e[j].to];
}
for(int i = 1; i < n; ++i)
{
int pos = i;
for(int j = i + 1; j < n; ++j)
if(fabs(f[j][i]) > fabs(f[pos][i])) pos = j;
if(pos != i) swap(f[i], f[pos]);
db tp = f[i][i];
if(fabs(tp) > eps) for(int j = i; j <= n; ++j) f[i][j] /= tp;
for(int j = i + 1; j < n; ++j)
{
db tp = f[j][i];
for(int k = i; k <= n; ++k) f[j][k] -= f[i][k] * tp;
}
}
for(int i = n - 1; i; --i)
{
ans[i] = f[i][n];
for(int j = i - 1; j; --j) f[j][n] -= f[j][i] * f[i][n];
}
for(int i = 1; i <= m; ++i) t[i].w = ans[t[i].x] / du[t[i].x] + ans[t[i].y] / du[t[i].y];
sort(t + 1, t + m + 1);
db sum = 0;
for(int i = 1; i <= m; ++i) sum += t[i].w * i;
printf("%.3lf
", sum);
return 0;
}