[hdu4035] Maze【概率dp 数学期望】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4035

真的是一道好题，题解比较麻烦，我自己在纸上写了好大一块草稿才搞出来，不用公式编辑器的话就很难看清楚，所以不上题解啦，贴一个题解的链接：http://blog.csdn.net/balloons2012/article/details/7891054

注意此题卡精度，我一开始eps是1e-8，WA掉了，开到了1e-10，AC~，真是烦卡精度的题。

#include <cstdio>

#include <cstring>

#include <cmath>

const int maxn = 20005;

int T, n, t1, t2, k[maxn], e[maxn];

int head[maxn], to[maxn << 1], next[maxn << 1], lb, out[maxn];

double a[maxn], b[maxn], c[maxn];

inline void ist(int aa, int ss) {

	to[lb] = ss;

	next[lb] = head[aa];

	head[aa] = lb;

	++lb;

	++out[aa];

}

bool dfs(int r, int p) {

	if (r > 1 && out[r] == 1) {

		a[r] = (double)k[r] / 100.0;

		b[r] = c[r] = (double)(100 - k[r] - e[r]) / 100.0;

		return true;

	}

	for (int j = head[r]; j != -1; j = next[j]) {

		if (to[j] != p) {

			dfs(to[j], r);

			a[r] += a[to[j]];

			b[r] += b[to[j]];

			c[r] += c[to[j]];

		}

	}

	double tem = 1.0 - (100 - k[r] - e[r]) * b[r] / 100.0 / out[r];

	if (fabs(tem) < 1e-10) {

		return false;

	}

	a[r] = ((k[r] / 100.0) + (100 - k[r] - e[r]) * a[r] / 100.0 / out[r]) / tem;

	b[r] = (100 - k[r] - e[r]) / 100.0 / out[r] / tem;

	c[r] = ((100 - k[r] - e[r]) / 100.0 + (100 - k[r] - e[r]) * c[r] / 100.0 / out[r]) / tem;

	return true;

}

int main(void) {

	//freopen("in.txt", "r", stdin);

	scanf("%d", &T);

	for (int kase = 1; kase <= T; ++kase) {

		printf("Case %d: ", kase);

		memset(head, -1, sizeof head);

		memset(next, -1, sizeof next);

		lb = 0;

		memset(out, 0, sizeof out);

		memset(a, 0, sizeof a);

		memset(b, 0, sizeof b);

		memset(c, 0, sizeof c);

		scanf("%d", &n);

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

			scanf("%d%d", &t1, &t2);

			ist(t1, t2);

			ist(t2, t1);

		}

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

			scanf("%d%d", k + i, e + i);

		}

		if (dfs(1, 0) && fabs(1.0 - a[1]) > 1e-10) {

			printf("%f\n", c[1] / (1.0 - a[1]));

		}

		else {

			puts("impossible");

		}

	}

	return 0;

}