[USACO10HOL]DOtP 题解

第一道应用高斯消元来解$dp$数组的题，感觉很妙。

这玩意没法$dp$…考虑套路的转化$dp$类型。
也就是$dp$出每个点期望经过次数，然后$\times (p/q)$就是概率。
咋$dp$？
设$dp[u]$为$u$点的期望经过次数。
有：

$dp[u]=[\sum_{(v,u) \in E}(1-p/q)\times(1/deg[v])\times dp[v]] + [u == 1]$

含义是，从$v$转移到$u$.由于$dp[v]$为$v$的期望经过次数，那么每次经过它都有$(1-p/q)\times(1/deg[v])$的概率成功到达$u$，那么单方面$v$对$dp[u]$的贡献就如上面公式所示了。

由于期望的线性性，可以直接加起来。

由于无向图上的$dp$顺序十分混乱，可以把$dp[1…n]$当作$n$个未知数，把转移方程当作方程，$gauss$消元$solve$一下即可。

（特别注意：由于$1$点一开始就经过了一次，真正$dp$出来之后$dp[1]$要比原始数值多$1$，需要在高斯消元方程组中体现一下）

/**
 * @Author: Mingyu Li
 * @Date:   2019-03-18T21:37:38+08:00
 * @Last modified by:   Mingyu Li
 * @Last modified time: 2019-03-18T21:40:36+08:00
 */
#include <bits/stdc++.h>
#define Go(i , x , y) for(register int i = x; i <= y; i++)
#define God(i , y , x) for(register int i = y; i >= x; i--)

// 设f[u] : 访问节点u的期望次数
// f[u] = \sum(1 - p / q) * f[v]
// 则显然有ans[u] = f[u] * (p/q)
// 特判1位置
// 列出来n个方程 高斯消元求f
// 最后乘个(p/q)

const int N = 300 + 10;
int n , m , p , q , u , v , deg[N];
double g[N][N];
bool w[N][N];

void Gauss() {
  Go(i , 1 , n) {
    int now = i;
    Go(j , i+1 , n) if(fabs(g[now][i]) < fabs(g[j][i])) now = j;
    Go(j , 1 , n+1) std::swap(g[i][j] , g[now][j]);

    Go(j , i+1 , n+1) g[i][j] /= g[i][i];
    g[i][i] = 1;
    Go(j , i+1 , n) {
      Go(k , i+1 , n+1) {
        g[j][k] -= g[j][i] * g[i][k];
      }
      g[j][i] = 0;
    }
  }// 构建上三角矩阵
  God(i , n , 1) {
    Go(j , i+1 , n) g[i][n+1] -= g[i][j] * g[j][n+1];
    g[i][n+1] /= g[i][i];
    g[i][i] = 1;
  }
}
int main() {
  scanf("%d%d%d%d", &n, &m, &p, &q);
  double weight = (1.0 * p) / (1.0 * q);
  Go(i, 1, m) {
    scanf("%d%d", &u, &v);
    w[u][v] = 1; w[v][u] = 1;
    ++deg[u]; ++deg[v];
  }

  // 构建高斯消元方程组

  Go(i, 1, n) {
    g[i][i] = -1;
    // ..... - f[u] + ...... = 0
    Go(j, 1, n) if(w[i][j] == 1) g[i][j] += (1.0 - weight) * (1.0 / (double)(deg[j]));
  }

  g[1][n + 1] = -1;
  Gauss();
  Go(i , 1 , n) std::cout << std::fixed << std::setprecision(9) << g[i][n+1] * weight << "\n";
  return 0;
}

# 概率期望dp, 高斯消元

[USACO10HOL]DOtP 题解

评论

分类

Your browser is out-of-date!