爱站程序员基地***
Roundgod and Milk Tea
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 nnn classes participating in this festival, where the iiith class has aia_iai students and will make bib_ibi 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 TTT (1≤T≤25)(1 \\leq T \\leq 25)(1≤T≤25), denoting the number of test cases.
Each test case starts with a line of a single integer nnn (1≤n≤106)(1 \\leq n \\leq 10^6)(1≤n≤106), the number of classes. For the next nnn lines, each containing two integers a,ba, ba,b (0≤a,b≤109)(0 \\leq a, b \\leq 10^9)(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 nnn over all test cases does not exceed 6×1066 \\times 10^66×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
题目大意：
有n个班级，每班有ai个人，能够生产bi杯奶茶，每个班的学生不能喝自己班的奶茶，只能喝别的班的奶茶，问最多有多少学生能够喝到奶茶
正解： 运用Hall’s marriage theorem定理：
设二部图G=<V1,V2,E>中, 如果存在t≥1, 使得V1中每个顶点至少关联 t 条边,而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配.
代码：
#include<cstdio>#include<algorithm>using namespace std;#define ll long longll a[1000005],b[1000005],t,n,ans,sum;int main(){scanf(\"%lld\",&t);while(t--){scanf(\"%lld\",&n);ans=0;sum=0;for(int i=1;i<=n;i++){scanf(\"%lld%lld\",a+i,b+i);ans+=a[i];}for(int i=1;i<=n;i++){b[i]=min(b[i],ans-a[i]);sum+=b[i];}printf(\"%lld\\n\",min(ans,sum));}}
