1 solutions

  • 0
    @ 2026-9-18 18:28:30

    题目简述:给定一张 nn 个点 mm 条边的无向图,要求找到两个点 u,vu,v 满足它们间的边不相交路径有至少 ⌈m/(n−1)⌉\lceil m/(n-1)\rceil 条。

    看到 n−1n-1 联想到 nn 个点的树恰好就是 n−1n-1 条边,或者说 nn 个点的森林最多只有 n−1n-1 条边。这启发我们去维护若干棵森林。

    具体而言使用 kruskal 的方法维护至少 ⌈m/(n−1)⌉\lceil m/(n-1)\rceil 个 nn 个点的森林,初始所有森林都是没有边的,然后一条边一条边地加入森林中,每次加入边都将其添加到尽可能靠前的一个森林中去。

    由于前 ⌈m/(n−1)⌉−1\lceil m/(n-1)\rceil-1 个森林最多只能容纳 (⌈m/(n−1)⌉−1)(n−1)<m(\lceil m/(n-1)\rceil-1)(n-1)<m 条边,所以最后一个森林中一定至少包含一条边,也就是说在最后一个森林中至少存在 u≠vu\ne v 满足 u,vu,v 中至少有一条路径。

    注意到由于每次添加边我们都是将其添加到尽可能靠前的森林中去的,所以如果 u,vu,v 在第 ii 个森林中连通,那么它必然在第 i−1i-1 个森林中连通,否则容易导出矛盾。由此我们直到对于最后一个森林中任意两个连通的点 u,vu,v,它们在前面的森林中都连通,所以每个森林中取一条路径即可构成 ⌈m/(n−1)⌉\lceil m/(n-1)\rceil 条边不相交路径了。

    额外需要注意的就是将边加入尽可能靠前的森林的时候不能直接枚举,这样时间复杂度至少是 O(m2/n)O(m^2/n) 的,当 nn 比较小 mm 比较大的时候会超时,而根据我们维护的森林结构性质,可以使用二分的手段来找到应该加入哪个森林中,这样时间复杂度不超过 O(mlog⁡m)O(m\log m)。

    • 1

    Information

    ID
    36
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By