ICPC沈阳网络赛B.Dudu's maze

发表于 | 阅读数

题意：

冗长的题面，不小心读错就容易直接暴毙

废话不多说，给定一个图（有重边），给定有K个房间是怪物房间，怪物房间只能走一次。并且走到那里之后，等概率走到其他房间。每个除了怪物房间，都有糖果，求获得糖果的期望。（注意是求期望最大值：因为此始终想不懂样例，卑微）（并且不可以连续走两个怪物房间。
看懂题目就很简单。把图分成很多联通块，答案就是

乱搞下就过了

代码 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N];
int n;
int fa[N], sum[N], m, k, v[N], mo[N];
int find(int x)
{
    if (fa[x] != x)
        return fa[x] = find(fa[x]);
    return x;
}
void unit(int x, int y)
{
    int xx = find(x);
    int yy = find(y);
    if (xx > yy)
    {
        fa[xx] = yy;
        sum[yy] += sum[xx];
    }
    else if (xx < yy)
    {
        fa[yy] = xx;
        sum[xx] += sum[yy];
    }
}
void init()
{
    for (int i = 1; i <= n; i++)
        fa[i] = i, sum[i] = 1;
    for (int i = 1; i <= n; i++)
        g[i].clear(), v[i] = 0;
}
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {

        double ans = 0;
        scanf("%d%d%d", &n, &m, &k);
        init();
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 1; i <= k; i++)
        {
            scanf("%d", &mo[i]);
            v[mo[i]] = 1;
        }

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < g[i].size(); j++)
                if (v[i] == 0 && v[g[i][j]] == 0)
                    unit(i, g[i][j]);

        for (int i = 1; i <= k; i++)
        {
            int u = mo[i];
            bool flag = 0;
            for (int j = 0; j < g[u].size(); j++)
                if (find(g[u][j]) == 1)
                    flag = 1;

            if (!flag)
                continue;
            double tmp = 0;
            for (int j = 0; j < g[u].size(); j++)
                if (find(g[u][j]) != 1 && v[g[u][j]] == 0)
                    tmp += sum[find(g[u][j])] / (1.0 * g[u].size());
            ans = max(tmp, ans);
        }
        printf("%.6lf\n", ans + 1.0 * sum[1]);
    }
}