婚庆网站建设目的,如何缩小wordpress文字边距,嘉兴cms建站模板,莱芜都市网官网Maze http://acm.hdu.edu.cn/showproblem.php?pid4035 分析#xff1a; 在树上走来走去#xff0c;然后在一个点可以k的概率回到1#xff0c;可以e的概率走出去#xff0c;可以1-k-e的概率走到其他的位置#xff08;分为父节点和子节点讨论#xff09;。 转移方程就是4035 分析 在树上走来走去然后在一个点可以k的概率回到1可以e的概率走出去可以1-k-e的概率走到其他的位置分为父节点和子节点讨论。 转移方程就是$dp[i] dp[1] \times k 0 \times e \frac{1 - k - e}{deg[i]} \times (dp[fa]1) \sum\limits_{j∈child[i]}\frac{1 - k - e}{deg[i]} \times (dp[j]1)$ 发现式子没法转换有后效性然后式子只与$dp[1],dp[fa],dp[child[i]]$有关系可以写成统一的格式$dp[i] A_i \times dp[1] B_i \times dp[fa] C_i$ 这样写完了发现$A,B,C$就可以从它的子节点转移了然后可以从叶子节点推到根。最后$dp[1] \frac{C[1]}{1-A[1]}$。 https://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.html 代码 1 #includecstdio2 #includealgorithm3 #includecstring4 #includecmath5 #includeiostream6 #includecctype7 #includeset8 #includevector9 #includequeue
10 #includemap
11 using namespace std;
12 typedef long long LL;
13
14 inline int read() {
15 int x0,f1;char chgetchar();for(;!isdigit(ch);chgetchar())if(ch-)f-1;
16 for(;isdigit(ch);chgetchar())xx*10ch-0;return x*f;
17 }
18
19 const int N 10010;
20 const double eps 1e-10;
21
22 double A[N], B[N], C[N], k[N], e[N];
23 vectorint T[N];
24
25 bool dfs(int u,int fa) {
26 double m 1.0 * T[u].size();
27 A[u] k[u], B[u] (1 - k[u] - e[u]) / m, C[u] 1 - k[u] - e[u];
28 double t 0;
29 for (int i0; im; i) {
30 int v T[u][i];
31 if (v fa) continue;
32 if (!dfs(v, u)) return false;
33 A[u] (1 - k[u] - e[u]) / m * A[v];
34 C[u] (1 - k[u] - e[u]) / m * C[v];
35 t (1 - k[u] - e[u]) / m * B[v];
36 }
37 if (fabs(1 - t) eps) return false;
38 A[u] / (1 - t), B[u] / (1 - t), C[u] / (1 - t);
39 return true;
40 }
41
42 int main() {
43 for (int Caseread(),t1; tCase; t) {
44 int n read();
45 for (int i1; in; i) T[i].clear();
46 for (int i1; in; i) {
47 int u read(), v read();
48 T[u].push_back(v), T[v].push_back(u);
49 }
50 for (int i1; in; i) {
51 int a read(), v read();
52 k[i] (double)a / 100.0;
53 e[i] (double)v / 100.0;
54 }
55 printf(Case %d: ,t);
56 if (dfs(1, 0) fabs(A[1] - 1) eps)
57 printf(%.10lf\n,C[1] / (1 - A[1]));
58 else puts(impossible);
59 }
60 return 0;
61 } 转载于:https://www.cnblogs.com/mjtcn/p/9638853.html
