白菜Oj 1122: [视频]最大匹配1（二分图）（元问题byscy）：公牛母牛配

题目描述

【问题背景】
n只公牛和m只母牛，
某些公牛和某些母牛互相喜欢。
但最后一只公牛只能和一只母牛建立一对一匹配。
要使得最后牛群匹配对数最大。
【输入】
第一行三个整数n, m，k( 1<= n, m <= 10000，0< k <= 100000）。
下来k行，每行两个整数 x，y，表示一条边，连接X集合中x点和Y集合的y点。
【输出】
只有一行。输出一个整数，表示牛群匹配对数最大值.

input:
5 5 9
1 2
2 2
2 3
2 5
3 1
3 3
4 1
5 3
5 4
output
5

注意公牛和母牛的编号有可能一样，给母牛编号+10000，避免重复编号问题

#include<iostream>  
#include<cstdio>  
#include<math.h>  
#include<cstring>  
#include<algorithm>  
#include<queue>  
#include<set>  
#include<vector>  
using namespace std;  
vector<int> v[30000];  
int u[30000]={0};  
int match[30000]={0};  
int dfs(int x){  
    for(int i=0;i<v[x].size();i++){  
        int num=v[x][i];  
        if(u[num]==0){  
            u[num]=1;  
            if(match[num]==0||dfs(match[num])){  
                match[num]=x;  
                return 1;  
            }  
        }   
    }  
    return 0;  
}  
int main(){  
    int n,m,k,sum=0;
	cin>>n>>m>>k;
	while(k--){
		int a,b;
		cin>>a>>b;
		b+=10000;
		v[a].push_back(b);
		v[b].push_back(a);
	} 
	for(int i=1;i<=n;i++){
		for(int j=10001;j<=10000+m;j++) u[j]=0;
		
		if(dfs(i)) sum++;
	}
	cout<<sum;
    return 0;  
}