Roundgod and Milk Tea[hdu6667]

题意

有 $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$。

程序

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