Roundgod and Milk Tea[hdu6667]

发表于 2019-12-29 分类于 hdu

有 $n$ 个班，每个班 $a_{i}$ 名学生，共做了 $b_{i}$ 杯奶茶。每个学生最多喝一杯奶茶，但不能喝本班的。问最多有多少个学生能喝到奶茶。

$n \leq 10^{6}, 0 \leq a_{i}, b_{i} \leq 10^{9}$

这道题让我学会了 Hall定理。。。

Hall定理详见：Hall定理

首先先建个二分图，每个班的每个学生代表的点都向别班的每杯奶茶连边，

题目转换成了求该二分图的最大匹配。

Hall定理的推论：最大匹配数 = $| X | - max (| W | - | N_{g} (W) |)$ 。

设 $Q = | W | - | N_{g} (W) |$ ，

下面考虑如何求 $Q$ 的最大值。

分三种情况讨论：

1， $| W | = 0$ ，此时 $Q = 0$ 。

2， $W$ 内只有第 $i$ 个班的学生，此时 $| N_{g} (W) | = (\sum b_{j}) - b_{i}$ ，为了让 $| W |$ 最大化， $| W |$ 应为 $a_{i}$ ，此时 $Q = a_{i} + b_{i} - (\sum b_{j})$ 。

3， $W$ 内有多个班的学生，此时 $| N_{g} (W) | = \sum b_{i}$ ，为了让 $| W |$ 最大化， $| W |$ 应为 $\sum a_{i}$ ，此时 $Q = (\sum a_{i}) - (\sum b_{i})$ 。

所以答案为： $(\sum a_{i}) - Q$ 。

学过编程的人都能写出来，懒得贴了。