poj 3041 Asteroids (匈牙利算法---二分圖最大匹配)

#include<iostream>
#include<vector>
using namespace std;
const int MAXN=501*2;
vector<int> G[MAXN];
int N,K;
int match[MAXN];
bool used[MAXN];

void add_edge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v){
	used[v]=1;
	for(int i=0;i<G[v].size();i++){
		int u=G[v][i],w=match[u];
		if(w<0 || !used[w] && dfs(w)){ 
			match[u]=v;
			match[v]=u;
			cout<<u<<" "<<v<<endl; 
			return 1;
		}
	}
	return 0;
}
int main()
{
	while(cin>>N>>K){
		for(int i=0;i<K;i++){
			int u,v;
			cin>>u>>v;
			add_edge(u,v+N);
		}
		int res=0;
		memset(match,-1,sizeof(match));
		for(int v=1;v<=N*2;v++){
			if(match[v]<0){
				memset(used,0,sizeof(used));
				if(dfs(v)) res++;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}