BZOJ 3143: [HNOI2013]游走 – [概率DP/高斯消元]

题目传送门(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 
#include 
#include 
#include 
#include 
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])= 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原创, 转载必须以链接形式注明>原文链接<