BZOJ 3566 概率充电器(树形概率DP)

题面

分析

定义f(i)f(i)f(i)为iii点不被点亮的概率，p(i)p(i)p(i)为iii自己被点亮的概率，p(i,j)p(i,j)p(i,j)表示i−ji-ji−j

这条边联通的概率，有f(i)=(1−p(i))∗∏i−j( 1−p(i,j)∗(1−f(j)) )\large f(i)=(1-p(i))*\prod_{i-j}(\ \ 1-p(i,j)*(1-f(j))\ \ )f(i)=(1−p(i))∗i−j∏( 1−p(i,j)∗(1−f(j)) )

可以看出，对于一个点iii，所有于它相连的点对它的影响是独立的，那么我们首先以111为根，只考虑儿子的影响做一次树形DPDPDP。然后再进行第二次DPDPDP，只考虑父亲的影响，具体做法只需要将父亲的f(fa)f(fa)f(fa)除以iii带来的影响就得到fafafa对iii的影响。见代码

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500005;

int n, fir[MAXN], cnt;

double p[MAXN];

struct edge {

	int to, nxt;

	double p;

}e[MAXN<<1];

inline void add(int u, int v, double wt) {

	e[++cnt] = (edge){v, fir[u], wt}; fir[u] = cnt;

	e[++cnt] = (edge){u, fir[v], wt}; fir[v] = cnt;

}

double dp[MAXN];

inline void dfs1(int u, int ff) {

	dp[u] = 1-p[u];

	for(int i = fir[u], v; i; i = e[i].nxt)

		if((v=e[i].to) != ff) dfs1(v, u), dp[u] *= 1-(1-dp[v])*e[i].p;

}

inline void dfs2(int u, int ff) {

	for(int i = fir[u], v; i; i = e[i].nxt) {

		if((v=e[i].to) != ff) {

			double tmp = 1 - (dp[u] ? dp[u]/(1-(1-dp[v])*e[i].p) : 0); //为了不除0

			dp[v] *= 1 - tmp*e[i].p;

			dfs2(v, u);

		}

	}

}

int main () {

	scanf("%d", &n);

	for(int i = 1, x, y, z; i < n; ++i)

		scanf("%d%d%d", &x, &y, &z), add(x, y, (double)z/100);

	for(int i = 1, x; i <= n; ++i)

		scanf("%d", &x), p[i] = (double)x/100;

	dfs1(1, 0);

	dfs2(1, 0);

	double ans = 0;

	for(int i = 1; i <= n; ++i)

		ans += 1-dp[i];

	printf("%.6f\n", ans);

}

关于在第二次dfsdfsdfs时的除法可能会除以零，是这样考虑的

若分母出现000，则说明dp[u]dp[u]dp[u]也一定是000，因为dp[u]dp[u]dp[u]在第一次dfsdfsdfs时本来就乘上了分母。那么此时tmp=1tmp=1tmp=1，也就是代表父亲一定会被点亮。
所以就判断一下dp[u]dp[u]dp[u]是否为000，再做除法就行了。

EOF\Large EOFEOF

巴特西

BZOJ 3566 概率充电器(树形概率DP)

题面

分析

CODE

最新文章

热门文章