A - Roundgod and Milk Tea 解题报告

题目链接：https://vjudge.net/contest/381753#problem/A
预备知识：
回顾二分图：
二分图：无向图G=(V,E),如果可以把结点集分成不相交的部分，即X和Y=V-X，使得每条边的其中一个端点在X中，另一个端点在Y中，则称图G是二分图。
二分图最大匹配
1.把二分图的两个结点集称为X和Y，有时也称为左边和右边，其中左边是X集，右边是Y集
2.匹配(matching)是指两两没有公共点的边集
3.最大匹配问题：
1.给出一个二分图，找一个边数最大的匹配；选尽量多的边(匹配边)，使得任意两条选中的边均没有公共点。(一个男人只能跟一个女人领证，考虑非诚勿扰)
4.如果图中所有点都是匹配点(匹配中的某一条边的端点)，则称这个匹配时完美匹配，此时|X|=|Y|
霍尔定理：
霍尔定理时判断二分图是否满足完美匹配的充要条件
首先要求|X|=|Y|,其中X是左边的点数，Y是右边的点数
对于任意的X的子集a都有|a|<=|b|,其中b是a能到达的点的并。
但仅仅是这样霍尔定理是没什么用的，霍尔定理有个NB的推论：
推论：假设两边的点集分别为X,Y,则二分图的最大匹配数为|X|-max{|W|-|N(W)|},其中W是X的子集。N(W)是W能到达的点的并。
这个推论就很厉害啦，对于一些特殊的题目，它可以免去建图而直接求最大匹配。
解题报告：
这道题把X就是班级里的同学，Y就是奶茶。每个同学不喝自己班的奶茶就是二分图中X中每个点与除自己班奶茶以外所有的Y中的点连一条边。然后求最多有多少同学能喝上奶茶，这就是二分图的最大匹配问题了。利用霍尔定理推论帮助线性求解二分图的最大匹配问题。

二分图的最大匹配为： |X|-max{|W|-|N(W)|}
设X是学生，Y为奶茶，则有两种情况。
当子集W中学生来自同一班级时，N(W)为|Y|-该班级的茶
当子集W中学生来自不同班级时，N(W)为|Y|

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+7;
template<class T>inline void read(T &res){char c;T flag=1;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;}
ll a[MAXN], b[MAXN];
int main()
{
    int T, n;
    read(T);
    while(T--) {
        read(n);
        ll suma = 0, sumb = 0, ans;
        for(int i = 1; i <= n; i++) {
            read(a[i]);read(b[i]), suma += a[i], sumb += b[i];
        }
        ans = min(suma, sumb);   //ans=suma-(suma-sumb)=sumb,但是考虑到最大匹配最多只能是min(suma,sumb)。
        for(int i = 1; i <= n; i++) {
            ans = min(ans, suma-a[i]+sumb-b[i]);    //因为是-max{|W|-|N(W)|}，因此这里是求min
        }
        printf("%lld\n",ans);
    }
}