【BZOJ3143】【Luogu P3232】 [HNOI2013]游走概率期望，图论

Love The Way You Lie 2022-01-09 10:51 210阅读 0赞

期望\\(DP\\)入门题目。

关键思想：无向边的转移作为有向边考虑。其他的就是直接上全期望公式。由于这个题目不是有向无环图，所以需要高斯消元搞一搞。

设每个点的期望经过次数是\\(g(x)\\)，那么有

\\\[g(u) = \\sum\_\{v\} \\frac\{1\}\{out(v)\}\*g(v)\\\]

特殊的，我们认为点\\(1\\)有一个一定经过的入边，且不考虑点\\(n\\)的所有出边。

这个\\(g\\)很好做啊，我们高斯消元搞一搞就好了。那边的期望经过次数\\(f(x)\\)也就显而易见。

\\\[f(x) = \\frac\{g(u)\}\{out(u)\} + \\frac\{g(v)\}\{out(v)\}\\\]

然后这个题就做完了。

#include <bits/stdc++.h> using namespace std; const int N = 500 + 5; int n, m, u[N * N], v[N * N], out[N]; vector <int> G[N]; double ans, f[N * N], g[N], mat[N][N]; void gauss_jordan () { for (int i = 1; i <= n; ++i) { int besti = i; for (int j = i; j <= n; ++j) { if (fabs (mat[besti][i]) < fabs(mat[j][i])) { besti = j; } } if (i != besti) swap (mat[i], mat[besti]); for (int j = 1; j <= n; ++j) { if (i == j) continue; double t = mat[j][i] / mat[i][i]; for (int k = i; k <= n + 1; ++k) { mat[j][k] -= mat[i][k] * t; } } } for (int i = 1; i <= n; ++i) { g[i] = mat[i][n + 1] / mat[i][i]; } } int main () { // freopen ("data.in", "r", stdin); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> u[i] >> v[i]; G[u[i]].push_back (v[i]); if (u[i] != n) out[u[i]]++; G[v[i]].push_back (u[i]); if (v[i] != n) out[v[i]]++; } mat[1][n + 1] = 1; for (int u = 1; u <= n; ++u) { mat[u][u] = 1; for (int i = 0; i < G[u].size (); ++i) { int v = G[u][i]; if (v == n) { mat[n][v] = -1.0 / out[v]; } else { mat[u][v] = -1.0 / out[v]; } } } gauss_jordan (); for (int i = 1; i <= m; ++i) { if (u[i] != n) f[i] += g[u[i]] / out[u[i]]; if (v[i] != n) f[i] += g[v[i]] / out[v[i]]; } sort (f + 1, f + 1 + m); for (int i = 1; i <= m; ++i) { ans += (m - i + 1) * f[i]; } cout << fixed << setprecision (3) << ans << endl; }

转载于:https://www.cnblogs.com/maomao9173/p/10941115.html