最近真的是智商跌到谷底，基本什么题都得看题解，就连这种水题都是在做HNOI2013 Day1的时候不小心瞄到wjmzbmr的题解的前提下才想出来。
如果我们知道每条边期望走过的次数，那么显然排序后贪心地标号即可。但是要知道每条边走过的次数还是比较困难的，我们可以考虑每个点i期望经过的次数p[i]。
显然，一个点能从除n外所有和他相邻的点j走过来，并且从j点走过来的概率为1/deg[j]。所以，p[i] = sigma(p[j]/deg[j])。另外，要注意到，点1到达次数明显会多1。
接下来我们就会发现，这是一个n-1个未知数、n-1个方程的方程组（为什么？因为不可能从n走到点i，并且n的期望次数为1），然后就可以很愉悦的高斯消元即可。
求出每个点的期望次数p[i]后，每条边(u, v)期望经过的次数ex[i]，ex[i] = p[u]/deg[u] + p[v]/deg[v]。当然了，因为还是不可能从n走出来，所以如果一个端点在n，那么就只有一端可以走。
然后排个序，编号就完了。
精度
这题的精度不知道如何破？反正我自己手测官方数据是过不去，交bzoj也过不去。后来改成long double和EPS = 1e-9就过了bzoj（但跟官方数据还是差0.1以上）。不管如何，反正是浪费了几乎一个小时……
代码
bzoj3143[Hnoi2013]游走
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
65
66
67
68
69
| #include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 501;
const long double EPS = 1e-9;
struct Edge
{
int v;
Edge *next;
} g[MAXN*MAXN], *header[MAXN];
void AddEdge(const int x, const int y)
{
static int LinkSize = 0;
Edge* const node = g+(LinkSize++);
node->v = y;
node->next = header[x];
header[x] = node;
}
int n, m, deg[MAXN], x[MAXN*MAXN], y[MAXN*MAXN], pos[MAXN*MAXN];
long double mat[MAXN][MAXN+1], ex[MAXN*MAXN];
void elimination(const int n)
{
for (int i = 1; i <= n; ++i)
{
int k = i;
for (int j = i+1; j <= n; ++j)
if (std::fabs(mat[j][i]) > std::fabs(mat[k][i]))
k = j;
for (int j = 1; j <= n+1; ++j)
std::swap(mat[i][j], mat[k][j]);
if (std::fabs(mat[i][i]) <= EPS)
continue;
for (int j = n+1; j >= i; --j)
mat[i][j] /= mat[i][i];
for (int j = 1; j <= n; ++j)
if (j != i)
for (int k = n+1; k >= i; --k)
mat[j][k] -= mat[j][i]*mat[i][k];
}
}
inline bool cmp(const int lhs, const int rhs) { return ex[lhs]-ex[rhs] > EPS; }
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d", x+i, y+i);
++deg[x[i]], ++deg[y[i]];
AddEdge(x[i], y[i]);
AddEdge(y[i], x[i]);
}
for (int i = 1; i <= n-1; ++i)
{
mat[i][i] = 1;
for (Edge *e = header[i]; e; e = e->next)
if (e->v != n)
mat[i][e->v] = static_cast<long double>(-1)/deg[e->v];
}
mat[1][n] = 1;
elimination(n-1);
for (int i = 0; i < m; pos[i] = i, ++i)
ex[i] = mat[x[i]][n]/deg[x[i]] + mat[y[i]][n]/deg[y[i]];
std::sort(pos, pos+m, cmp);
long double ans = 0;
for (int i = 0; i < m; ++i) ans += ex[pos[i]]*(i+1);
printf("%.3Lf", ans);
}
|
