2020-2021:teams:alchemist:mountvoom:halltheorem

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 01:06]
mountvoom
+++ 2020-2021:teams:alchemist:mountvoom:halltheorem [2020/05/12 10:29] (当前版本)
mountvoom
@@ 行 5: / 行 5: @@
 则定理描述为：二分图存在完美匹配，等价于对于$X$的任意子集$X^{'}$，与它们中任意点相连的$Y$的结点个数$\ge |X^{'}|$。
-[[https://codeforces.com/gym/102268/problem/D|Date]]
+[[https://codeforces.com/gym/102268/problem/D|gym102268D Dates]]
+**题意:**
+给你一张二分图，左边有$t$个位置，右边右$n$个带权点，第$i$个点与$[l_i, r_i]$所有点连边，匹配的值为匹配中右边点的权值和，求最大权匹配。
+其中，$1 \leq n, t \leq 3 \times 10^5, l_i \leq l_{i + 1}, r_i \leq r_{i + 1}$
+**题解:**
+将右边的点按照权值从大到小排序，依次加入查看有无完美匹配，有就选择否则跳过。按照我个人的理解，如果让一个权值更小的替换了当前某个已经选择的某个点，匹配数不会变多，答案也不会变优。
+于是，问题转化成了如何判定是否存在完全匹配，这就用到了霍尔定理，考虑右边的点中被选择的那些，选择其一个子集，判断是否所有子集的邻域（即与其相邻的点构成的集合）大小都比子集本身大。
+如果我们选择的子集对应的区间是不连续的，霍尔定理的条件成立等价于对于断点两边分别成立，所以只用考虑选取的子集对应的区间连续的情况。
+又因为$l_i \leq l_{i + 1}, r_i \leq r_{i + 1}$，也就是说只需要考虑选择的子集的编号连续的情况，即
+$\forall 1\le i< j\le n,[i,j]\text{中被选择的右侧点个数}\le [l_i,r_j]\text{中左侧点数量}$
+令$pre[i]$为$a[i]$的前缀和，$p[i]$表示$[1, i]$中已经被选择的右侧点的个数，公式等价于：
+$\forall 1\le i< j\le n, p[j]-p[i-1]\le pre[r_j]-pre[l_i-1]$
+即:
+$\forall 1\le i< j\le n, pre[l_i-1]-p[i-1]\le pre[r_j]-p[j]$
+于是可以对每个位置维护一个$pre[l_{i + 1} - 1] - p[i]$和$pre[r_i] - p[i]$，注意此时$i \in [0, n]$
+其中$pre[i]$是是定值，$p[i]$可以用线段树轻松维护，每次插入时只需要前检查$i < x$的$pre[l_i-1]-p[i-1]$的最大值和$i \ge x$的$pre[r_j]-p[j]$的最小值的关系即可。

2020-2021/teams/alchemist/mountvoom/halltheorem.1589216792.txt.gz · 最后更改: 2020/05/12 01:06 由 mountvoom