本人是退役ACMer,本Blog原则上不发ACM解题报告,因昨天网络赛汇总到的第5题Maze解题报告没有提供相应代码,我按照该解题报告写了一份代码,已经AC,代码供其他人参考。
解题报告的链接为:http://blog.163.com/scaulyd@126/blog/static/155226395201181183149326/,看代码请参照该解题报告。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <stdio.h> #include <vector> #include <math.h> using namespace std; const int N = 10001; double e[N], k[N]; vector<int> adj[N]; double A[N], B[N], C[N]; int n; bool search(int u, int fa) { if (adj[u].size() == 1 && fa != -1) {//叶子节点 A[u] = k[u]; B[u] = 1 - k[u] - e[u]; C[u] = 1 - k[u] - e[u]; return true; } A[u] = k[u]; B[u] = (1. - k[u] - e[u]) / adj[u].size(); C[u] = 1. - k[u] - e[u]; double tmp = 0; for (int i = 0; i < adj[u].size(); i++) { if (adj[u][i] == fa) continue; if (!search(adj[u][i], u)) return false; A[u] += A[adj[u][i]] * (1. - k[u] - e[u]) / adj[u].size(); C[u] += C[adj[u][i]] * (1. - k[u] - e[u]) / adj[u].size(); tmp += B[adj[u][i]] * (1. - k[u] - e[u]) / adj[u].size(); } if (fabs(tmp - 1) < 1e-10) return false; A[u] /= 1 - tmp; B[u] /= 1 - tmp; C[u] /= 1 - tmp; return true; } int main() { int T; int i, j; scanf("%d", &T); int ca = 1; while (T--) { scanf("%d", &n); for (i = 0; i < n; i++) { adj[i].clear(); } for (i = 0; i < n - 1; i++) { int s, t; scanf("%d%d", &s, &t); s--; t--; adj[s].push_back(t); adj[t].push_back(s); } for (i = 0; i < n; i++) { scanf("%lf%lf", k + i, e + i); e[i] /= 100.; k[i] /= 100.; } if (search(0, -1) && fabs(1 - A[0]) > 1e-10) { printf("Case %d: %f\n", ca++, C[0] / (1 - A[0])); } else { printf("Case %d: impossible\n", ca++); } } return 0; } |
本文来自Dora Blog,题目为2011 ACM ICPC 成都赛区网络赛 (HDU 4035) 解题报告补充,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读!
欢迎关注我的新浪微博:http://weibo.com/diaorui1987
One Response to “2011 ACM ICPC 成都赛区网络赛 (HDU 4035) 解题报告补充”
on 九月 12th, 2011 at 17:32 #
[...] 5 Maze http://blog.163.com/scaulyd@126/blog/static/155226395201181183149326/ http://diaorui.net/?p=238 [...]