OI

BZOJ 3143: [Hnoi2013]游走

Description

一个无向连通图，顶点从1编号到N，边从1编号到M。

小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。

现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

Input

第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1≤u,v≤N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10，100%的数据满足2≤N≤500且是一个无向简单连通图。

Output

仅包含一个实数，表示最小的期望值，保留3位小数。

Sample Input

3 3

2 3

1 2

1 3

Sample Output

3.333

HINT

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

Source

非官方数据

Solution

\(dp_i\)表示从点i出发期望次数。

注意\(dp_1\)要多经过一次，\(dp_n=0\)。

这个有n-1个变量的dp就用高斯消出来。

用这个dp可以求每条边期望经过次数。

\[e_i=dp_u/dig_u+dp_v/dig_v\]

（dig是度数）

把这个e排个序 从大到小标号即可。

Code

 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

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const double eps = 1e-7;
int n, m, u[505*505], v[505*505], d[505], h[505], cnte;
double a[505][505], f[505], g[505*505], ans;
struct edge_t { int fr, next; } edge[2*505*505];
void ins(int x, int y) {
	edge[++cnte].fr = x;
	edge[cnte].next = h[y];
	h[y] = cnte;
}
int main() {
	int i, j, k;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%d %d", u + i, v + i);
		++d[u[i]]; ++d[v[i]];
		ins(u[i], v[i]);
		ins(v[i], u[i]);
		a[u[i]][v[i]] = a[v[i]][u[i]] = -1.0;
	}
	for (i = 1; i < n; ++i) {
		for (j = 1; j < n; ++j)
			if (d[j]) a[i][j] /= d[j];
		a[i][i] = 1, a[i][n] = 0;
	}
	a[1][n] = 1;
	for (i = 1; i < n; ++i) {
		k = i;
		for (j = i+1; j < n; ++j)
			if (fabs(a[j][i]) > fabs(a[k][i])) k = j;
		if (fabs(a[k][i]) < eps) continue;
		if (k != i) for (j = i; j <= n; ++j) swap(a[i][j], a[k][j]);
		for (j = i+1; j < n; ++j) {
			double tmp = a[j][i] / a[i][i];
			for (k = i; k <= n; ++k)
				a[j][k] -= a[i][k] * tmp;
		}
	}
	for (i = n - 1; i > 0; --i) {
		for (j = i+1; j < n; ++j)
			a[i][n] -= a[i][j] * f[j];
		f[i] = a[i][n] / a[i][i];
	}
	for (int i = 1; i < n; ++i)
		if (d[i]) f[i] /= d[i];
	for (i = 1; i <= m; ++i)
		g[i] = f[u[i]] + f[v[i]];
	sort(g + 1, g + m + 1);
	for (i = 1; i <= m; ++i)
		ans += g[i] * (m-i+1);
	printf("%.3lf\n", ans);
}