Roundgod and Milk Tea

Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1534    Accepted Submission(s): 724

 

Problem Description
Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be n classes participating in this festival, where the ith class has ai students and will make bi cups of milk tea.

Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can't drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea?
 

 

Input
The first line of input consists of a single integer T (1≤T≤25), denoting the number of test cases.

Each test case starts with a line of a single integer n (1≤n≤106), the number of classes. For the next n lines, each containing two integers a,b (0≤a,b≤109), denoting the number of students of the class and the number of cups of milk tea made by this class, respectively.

It is guaranteed that the sum of n over all test cases does not exceed 6×106.
 

 

Output
For each test case, print the answer as a single integer in one line.
 

 

Sample Input 
 
1 2 3 4 2 1
 

 

Sample Output 
 
3
 

 

Source
 
题意：
 
 n 个班聚会，每个班出席人数为 ai ，制作的奶茶数为 bi 杯，每个人不可以喝自己班提供的奶茶，问最多有多少人可以喝上奶茶？
 
思路：
 
模拟了半天一直WA，咕了
 
（科普）
 
Hall定理：
 
二分图G中的两部分顶点集合分别为X, Y,假设有 |X|<=|Y|。G图存在完美匹配的充分必要条件是：X中的任意k个点至少与Y中的k
 
个点相邻，即对于X中的一个点集W ，令N(W)为W所连的点， 霍尔定理即对于任意W有 |W|<=|N(W)|
 
Hall定理的推论：
 
二分图的最大匹配为：|X|−max{|W|−|N(W)|}，其中W为X的任意子集。
 
 
设suma为总学生数，sumb为总的奶茶数。如果 |X| 是学生，|Y| 是奶茶（|X| <= |Y|）
 
（1）如果 |W| 都是同一个班的话，|N(W)| 就是除该班以外的奶茶数，暴力求suma - max(a[i] - (sumb - b[i])) ，
 
         即min(suma - a[i] + sumb - b[i])
 
（2）如果 |W| 中的学生不是同一个班的话，|N(W)| 就是 |Y|
 
         suma - max(|W| - sumb) 即 suma - (suma - sumb) = sumb，即选中所有的学生，但是这时学生数为suma，匹配数却是sumb，明显不符合题意
 
  
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 7;

int a[N], b[N];

int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        ll suma = 0, sumb = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &a[i], &b[i]);
            suma += 1ll * a[i];
            sumb += 1ll * b[i];
        }
        ll ans = min(suma, sumb);
        for(int i = 1; i <= n; ++i)
        {
            ans = min(ans, suma + sumb - 1ll * a[i] - 1ll * b[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}