2011 ACM ICPC 成都赛区网络赛 (HDU 4035) 解题报告补充

九月 12th, 2011 · · 算法艺术 One comment




本人是退役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