2019 icpc 沈阳网络赛 B Dudu's maze 并查集

题意

我们已知n个点，m条边，k个标记。可能存在重边，无自环（就是不存在 a->a，但存在环）
除了k个被标记的点，其他点都有一个糖果，并且这些点是可以任意的选择道路。被标记的点只能随机的被安排道路（只能被安排一次，下次遇到就结束）。先要求从1号屋开始，最多能拿多少糖果

分析

首先我们看到了随机，可想而知是个期望题。由于我们只有一次跳转的机会，这样会发现只有与1号屋相连的（直接或间接）怪兽屋才是有用的。大致就可以理解为，用怪兽屋去分割，对每个联通块进行缩点。然后找与1号屋相连的怪兽屋的最大贡献，当然最后在加上一号屋所在联通块的大小。
$贡献=\max \left(\frac{与怪兽屋相连的点所在联通块大小，该联通块内没一号屋}{与怪兽屋所连边的数量}\right)$贡献=max(与怪兽屋所连边的数量与怪兽屋相连的点所在联通块大小，该联通块内没一号屋​)
然后我们可以直接用并查集求解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5 + 5;
int fa[N], num[N], kk[N], n, m, k;
bool vis[N];
vector <int> G[N];
void init()
{
    for(int i = 0; i < N; i ++)
    {
        fa[i] = i;
        vis[i] = false;
        num[i] = 1;
        G[i].clear();
    }
}
int find(int x)
{
    if(x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --)
    {
        init();
        cin >> n >> m >> k;
        for(int i = 0; i < m; i ++)
        {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i = 0; i < k; i ++)
        {
            cin >> kk[i];
            vis[kk[i]] = true;
            num[kk[i]] = 0;
        }
        for(int i = 1; i <= n; i ++)
        {
            int size = G[i].size();
            for(int j = 0; j < size; j ++)
            {
                int a = i, b = G[i][j];
                if(vis[a] || vis[b])
                    continue;
                a = find(a);
                b = find(b);
                if(a != b)
                {
                    if(a == 1)
                    {
                        fa[b] = a;
                        num[a] += num[b];
                    }
                    else 
                    {
                        fa[a] = b;
                        num[b] += num[a];
                    }
                }
            }
        }
        double ma = 0;
        for(int i = 0; i < k; i ++)
        {
            int d = kk[i];
            int size = G[d].size();
            bool flag = false;
            for(int j = 0; j < size; j ++)
            {
                int a = G[d][j];
                a = find(a);
                if(a == 1)
                {
                    flag = true;
                    break;
                }
            }
            if(flag) 
            {
                double f = 0;
                for(int j = 0; j < size; j ++)
                {
                    int a = G[d][j];
                    a = find(a);
                    if(a == 1)
                        continue;
                    f += num[a] * 1.0 / size; 
                }
                ma = max(f, ma);
            }
        }
        ma += (double)num[1];
        cout << fixed << setprecision(8) << ma << endl;
    }
}