[2019杭电多校第八场][hdu6667]Roundgod and Milk Tea

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6667

题目大意是说n个班级，每个班级有ai人和bi杯茶，每个人只能喝其他班的茶并且只能喝一杯。问最多有多少人可以喝茶。

读完题就觉得是网络流or二分图，然后发现数据范围就萎了，开始想怎么转化模型，因为题目实际就是求每个人连其他班的茶之后跑二分图最大匹配。

然后想到了hall定理和推论，好像对于线性求解二分图蛮有帮助的，公式写出来大致就可以明白了。

PS:|X|为点集X的点数

hall定理：

二分图G中的两部分顶点集合分别为X, Y,假设有 |X|<=|Y|。G图存在完美匹配的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W所连的点，霍尔定理即对于任意W有 |W|<=|N(W)|

推论为：

二分图的最大匹配为：$|X|-max\left \{|W|-|N(W)|\right \}$，其中W为X的任意子集。

对于这题而言设X为学生，Y为茶，则有两种情况：

当子集W中学生为同一班级时，N(W)为|Y|-该班级的茶数。

当自己W中学生不为同一班级时，N(W)为|Y|。

所以暴力跑O(N)即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = 2e6 + ;

 ll a[maxn], b[maxn];

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n;

         ll suma = , sumb = , ans;

         scanf("%d", &n);

         for (int i = ; i <= n; i++)

             scanf("%lld%lld", &a[i], &b[i]), suma += a[i], sumb += b[i];

         ans = min(suma, sumb);

         for (int i = ; i <= n; i++)

             ans = min(ans, suma - a[i] + sumb - b[i]);

         printf("%lld\n", ans);

     }

 }

巴特西

[2019杭电多校第八场][hdu6667]Roundgod and Milk Tea

最新文章

热门文章