1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 500+5;
const double EPS = 1e-6;
struct Matrix
{
int n, m;
double __mat[N][N];
Matrix(int n = 0, int m = 0):n(n), m(m) { memset(__mat, 0, sizeof(__mat)); }
double* operator[] (const int i) { return __mat[i]; }
void change(int i, double r, int j) { for(int k = 1; k <= m; ++k) __mat[j][k] += __mat[i][k]*r; }
void exchange(int i, int j) { for(int k = 1; k <= m; ++k) swap(__mat[i][k], __mat[j][k]); }
}A, B;
int n, m, deg[N];
int u[N*N], v[N*N];
double f[N*N], ans;
void Gauss(Matrix &A, Matrix &B)
{
int n = A.n, p;
for(int i = 1, c = 1; i <= n; ++i)
{
for(p = c; p <= n&&fabs(A[c][i]) < EPS; ++p);
if(p == n+1) continue;
A.exchange(p, c); B.exchange(p, c);
for(int j = c+1; j <= n; ++j)
B.change(c, -A[j][i]/A[c][i], j),
A.change(c, -A[j][i]/A[c][i], j);
++c;
}
for(int i = n; i; --i)
{
B[i][1] /= A[i][i], A[i][i] = 1;
for(int j = i-1; j; --j) B[j][1] -= A[j][i]*B[i][1], A[j][i] = 0;
}
}
int main()
{
scanf("%d%d", &n, &m); A = Matrix(n-1, n-1); B = Matrix(n-1, 1);
for(int i = 1; i <= m; ++i)
{
scanf("%d%d", &u[i], &v[i]);
++deg[u[i]], ++deg[v[i]];
}
for(int i = 1; i < n; ++i) A[i][i] = 1; B[1][1] = 1;
for(int i = 1; i <= m; ++i)
{
if(deg[v[i]]&&v[i] != n) A[u[i]][v[i]] += -1.0/deg[v[i]];
if(deg[u[i]]&&u[i] != n) A[v[i]][u[i]] += -1.0/deg[u[i]];
}
Gauss(A, B);
for(int i = 1; i <= m; ++i)
{
if(u[i] != n) f[i] += B[u[i]][1]/deg[u[i]];
if(v[i] != n) f[i] += B[v[i]][1]/deg[v[i]];
}
sort(f+1, f+1+m);
for(int i = 1; i <= m; ++i) ans += (m-i+1)*f[i];
printf("%.3lf\n", ans);
return 0;
}
|