1 solutions

  • 0
    @ 2026-9-18 18:32:42

    结论:最终一定能取到最大匹配。

    可以通过递归完成构造。

    Key Obeservation:总存在一个最大匹配,使得存在一个学生选到了其最喜欢的小班课。

    证明:令 (p1,q1),(p2,q2)…(pk,qk)(p_1,q_1),(p_2,q_2)\dots (p_k,q_k) 为一组最大匹配。 r1,r2…rkr_1,r_2\dots r_k 分别为 p1,p2…pkp_1,p_2\dots p_k 最喜欢的小班课。

    若存在 rir_i 不为任何一个 qjq_j,那么直接将 qiq_i调整为 rir_i 即可。

    否则 (pi,qi),(pi,ri)(p_i,q_i),(p_i,r_i) 均连边后构成的二分图,其恰好有 2k2k 个结点和 2k2k 条边。而左部每个点度数为 22,可以重复找到右部度数为 11 的点 qiq_i,删去 pip_i 和 qiq_i,因此会被删掉 22 个点和 22 条边,可以递归下去。最终一定所有点度数都为 22,构成若干个环。对于每个环上所有点将 qiq_i 均调整为 rir_i 即可。

    于是我们有如下做法:每次任意找到一个选到其最喜欢的小班课的学生,将其放入队列的第一个,将该学生删除,课容量减一,如果课容量为 00 删去该课程。然后递归构造。

    实际实现中,首先需要一个二分图匹配,这里的复杂度是 O(n3)O(n^3)。上述的证明可以直接实现成构造,单次构造是 O(n)O(n) 的,复杂度为 O(n2)O(n^2)。具体实现还可以用一个小技巧,即仅保留 (pi,qi),(pi,ri)(p_i,q_i),(p_i,r_i) 这些边之后随机顺序做二分图匹配,这样每个环有 12\frac{1}{2} 的顺序改变顺序,每一次匹配是 O(n2)O(n^2) 的,期望复杂度同样也是 O(n2)O(n^2) 的。

    • 1

    Information

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