首先高斯消元解出每个点被走到的概率
注意到这里走到$n$就停下来了，所以$P(n) = 0$
解出来以后，给每条边$(u, v)$赋边权$P(u) + P(v)$即可，然后直接贪心
/**************************************************************
Problem: 3143
User: rausen
Language: C++
Result: Accepted
Time:680 ms
Memory:6792 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> using namespace std;
typedef double lf;
const int N = ;
const int M = N * N;
const lf eps = 1e-; int read(); int n, m, tot;
int deg[N];
lf a[N][N], ans[N], w[M];
lf Ans; struct edge {
int x, y;
} E[M]; inline void Add_Edges(int x, int y) {
E[++tot].x = x, E[tot].y = y;
a[x][y] = a[y][x] = -1.0;
++deg[x], ++deg[y];
} void gauss(int n) {
int i, j, k;
lf tmp;
for (i = ; i <= n; ++i) {
for (k = i, j = i + ; j <= n; ++j)
if (fabs(a[j][i]) > fabs(a[k][i])) k = j;
if (fabs(a[k][i]) < eps) continue;
for (j = i; j <= n + ; ++j) swap(a[i][j], a[k][j]);
for (k = i + ; k <= n; ++k)
for (tmp = -a[k][i] / a[i][i], j = i; j <= n + ; ++j)
a[k][j] += a[i][j] * tmp;
}
for (i = n; i; --i) {
for (j = i + ; j <= n; ++j)
a[i][n + ] -= a[i][j] * ans[j];
ans[i] = a[i][n + ] / a[i][i];
}
} int main() {
int i, j;
n = read(), m = read();
for (i = ; i <= m; ++i)
Add_Edges(read(), read());
for (i = ; i < n; ++i) {
for (j = ; j < n; ++j)
if (deg[j]) a[i][j] = a[i][j] / deg[j];
a[i][i] = , a[i][n] = ;
}
a[][n] = ;
gauss(n - );
for (i = ; i <= n; ++i)
if (deg[i]) ans[i] /= deg[i];
for (i = ; i <= m; ++i)
w[i] = ans[E[i].x] + ans[E[i].y];
sort(w + , w + m + );
for (i = ; i <= m; ++i) Ans += w[i] * (m - i + );
printf("%.3lf\n", Ans);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}