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

期望\(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;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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