题目传送门(BZOJ)

题解 :

题目让我们求期望得分最小, 那么比较明显的是要把期望经过次数多的边的权值赋小
所以我们只需要求出边的期望经过次数, 然后排序并给他们赋编号, 再用期望\times权值的方式统计答案即可
然鹅边太多了, 不好求, 求点比较容易, 设 deg[u] 为点 u 的度数
每条边 (u, v) 的期望就是 \frac{f[u]}{deg[u]}+\frac{f[v]}{deg[v]}
现在要解决的问题就是点的期望了
f[x] 为点 x 的期望经过次数
那么 f[x] = \sum\limits_{y\to x}\frac{f[y]}{deg[y]}
这个转移是有环的, 按这个式子列出 n 个方程, 做高斯消元即可获得每个点的度数
转化成高斯消元矩阵就相当于把右边的项移动到左边
然后有形如 :
1f[1]+b_1f[2]+c_1f[3] = 0
a_2f[1]+1f[2]+c_2f[3] = 0
a_3f[1]+b_3f[2]+1f[3] = 0
直接消元求解即可
需要注意的是边界状态 :
N 意味着停止, 所以所有的转移是不应该包含 N 的, 且 N 的期望是 0
强制从 1 开始, 所以 1 的初始期望次数是 1

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510;#define f2 double#define rev(i, p) for(EDGE* i = h[p]; i; i = i->next)struct EDGE { int to; EDGE *next;}*h[N], e[N*N];struct ROAD { int u, v;}a[N*N];inline void addEdge(int u, int v) { static int _; EDGE* t = &e[++_]; t->to = v, t->next = h[u], h[u] = t;}inline f2 fabs(f2 x) { return x > 0 ? x : -x;}f2 f[N][N], val[N*N];int deg[N], n, m;void Gauss() { for(int i = 1; i < n; i ++ ) { int cur = i; for(int j =i+1;j <= n; j ++ ) if(fabs(f[cur][i])<fabs(f[j][i])) cur = j; for(int j = i; j <= n; j ++ ) swap(f[i][j], f[cur][j]); for(int j = n; j >= i; j -- ) f[i][j] /= f[i][i]; for(int j = 1; j < n; j ++ ) if(i != j) { for(int k = n; k >= i; k -- ) f[j][k] -= f[j][i]*f[i][k]; } }}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++ ) { int u, v; scanf("%d%d", &u, &v); a[i].u = u, a[i].v = v; addEdge(u, v); addEdge(v, u); deg[u] ++, deg[v] ++; } f[1][n] = 1; for(int i = 1; i < n; i ++ ) { f[i][i] = 1; rev(j, i) if(j->to != n) { f[i][j->to] = -1.0/deg[j->to]; } } Gauss(); for(int i = 1; i <= m; i ++ ) { int u = a[i].u, v = a[i].v; if(u != n) val[i] += f[u][n]*(1.0/deg[u]); if(v != n) val[i] += f[v][n]*(1.0/deg[v]); } sort(val+1, val+m+1); reverse(val+1, val+m+1); f2 ans = 0; for(int i = 1; i <= m; i ++ ) ans += val[i]*i; printf("%.3f\n", ans); return 0;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<