題干：

有n個人，m條狗，然后會給出有一些人不喜歡一些狗就不會購買，問最多能賣多少狗。。

Input

There is a single integer T in the first line of the test data indicating that there are T(T≤100) test cases. In the first line of each test case, there are three numbers n, m(0≤n,m≤100) and e(0≤e≤n*m). Here, n and m represent the number of customers and the number of pets respectively.

In the following e lines of each test case, there are two integers x(1≤x≤n), y(1≤y≤m) indicating that customer x is not interested in pet y, such that x would not buy y.

Output

For each test case, print a line containing the test case number (beginning with 1) and the maximum number of pets that can be sold out.

Sample Input

1 2 2 2 1 2 2 1

Sample Output

Case 1: 2

解題報告：

? ?隨便匈牙利一下。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e2 + 5; int nxt[MAX]; bool line[MAX][MAX]; bool use[MAX]; int n,m,e; bool find(int x) {for(int i = 1; i<=m; i++) {if(!use[i]&& line[x][i]) {use[i]=1;if(!nxt[i] || find(nxt[i])) {nxt[i] = x;return 1;}}}return 0; }int match() {int res = 0 ;for(int i = 1; i<=n; i++) {memset(use,0,sizeof use);if(find(i)) res++;}return res; } int main() {int t,iCase=0;cin>>t;while(t--) {memset(line,1,sizeof line);memset(nxt,0,sizeof nxt);scanf("%d%d%d",&n,&m,&e);for(int a,b,i = 1; i<=e; i++) {scanf("%d%d",&a,&b);line[a][b]=0;}printf("Case %d: %d\n",++iCase,match());}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【FZU - 2039】Pets（二分图匹配，水题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。