Doveqise

Doveqise

万事皆虚,诸行皆允

CF437D The Child and Zoo 题解

posted on 2019-10-07 09:27:03 | under 题解 |

我在怀疑这道题的颜色
来补一下模拟赛的T1
我就按着模拟赛的数据范围给出一步一步的做法。
把模拟赛数据范围贴上来(

对于10%的测试数据,满足 $2 \leq n \leq 10 , n - 1 \leq m \leq 20$
对于30%的测试数据,满足 $2 \leq n \leq 200 , n - 1 \leq m \leq 1000$
对于50%的测试数据,满足 $2 \leq n \leq 1000 , n - 1 \leq m \leq 20000$
对于100%的测试数据,满足 $2 \leq n \leq 100000 , n - 1 \leq m \leq 1000000$
$ 0 \leq a_i \leq 100000 ,1 \leq x_i,y_i \leq n,(x_i \neq y_i)$ ,保证是连通图且没有重边。

解法1:
暴力枚举点跑n遍 $Floyd$
分数:10pts(这时间复杂度有点惨

解法2:
随便想想珂以暴力枚举两点枚举所有路径
分数:30pts

解法3:
从每个点跑 $BFS$
分数:50pts

解法4:
并查集
通过观察可得所有的路径必在最大生成树上。
证明:若有一条满足题意的连接 $x$ 与 $y$ 的路径,且不在最大生成树上,那么由于这条路径不在最大生成树上,必定至少有一条边的边权 $ \leq $ 最大生成树上的边权,那么选择最大生成树上的路径不会更劣
$Q.E.D.$
然后 $Kruskal$ 跑最大生成树统计答案即可。
分数:100pts

细节见代码。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
typedef long long ll;
ll n, m, ans;
int val[maxn], s[maxn], fa[maxn], siz[maxn];
int hd[maxn], tot, vis[maxn];
struct edge
{
    int nxt, to;
} ed[maxm << 1];
int findfa(int x)
{
    return fa[x] == x ? x : fa[x] = findfa(fa[x]);
}
bool cmp(int a, int b)
{
    return val[a] > val[b];
}
void addedge(int x, int y)
{
    ed[++tot] = (edge){hd[x], y};
    hd[x] = tot;
}
signed main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; siz[i] = 1, i++)
        scanf("%d", &val[s[i] = fa[i] = i]);
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1, a, b; i <= m; i++)
    {
        scanf("%d%d", &a, &b);
        addedge(a, b);
        addedge(b, a);
    }
    for (int u = 1; u <= n; u++)
    {
        ll res = 0;
        for (int i = hd[s[u]]; i; i = ed[i].nxt)
        {
            int v = ed[i].to;
            if (!vis[v])
                continue;
            int p = findfa(s[u]), q = findfa(v);
            if (p == q)
                continue;
            res += 1ll * siz[p] * siz[q];
            fa[p] = q;
            siz[q] += siz[p];
        }
        ans += 1ll * res * val[s[u]];
        vis[s[u]] = 1;
    }
    printf("%lf\n", ans * 2.0 / (n * (n - 1)));
    return 0;
}