FZU2039 Pets 二分匹配

二分匹配的题目，建图比较重要，n个人m个宠物，接下来e行，每行两个数字x,y,代表编号为x的人不喜欢编号为y的宠物，意思就是x肯定不会选y，求最多可以卖出多少宠物，人跟宠物进行建图，可以构成一个二分匹配图，注意题目给的x,y是不能选的，所以在你建的图map里面 要跟一般的二分匹配题目反过来进行标记

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

const int N = 1000 + 5;

int n,m,e;
int mp[N][N];
bool vis[N];
int marry[N];

void clear() {
	memset(mp,0,sizeof(mp));
	memset(marry,0,sizeof(marry));
}

int detal(int u) 
{ 
	for(int i=1;i<=m;i++) 
	{ 
		if(mp[u][i] || vis[i]) 
			continue; 
		vis[i]=1; 
		if(!marry[i] || detal(marry[i])) 
		{ 
			marry[i]=u; 
			return 1; 
		} 
	} 
	return 0; 
} 

int main() {
	int t;
	int Case = 0;
	scanf("%d",&t);
	while(t--) {
		clear();
		scanf("%d %d %d",&n,&m,&e);
		int x,y;
		for(int i=0;i<e;i++) {
			scanf("%d %d",&x,&y);
			mp[x][y] = 1;
		}
		int ans = 0;
		for(int i=1;i<=n;i++) {
			memset(vis,0,sizeof(vis));
			if(detal(i)) ans++;
		}
		printf("Case %d: %d\n",++Case,ans);
	}
	return EXIT_SUCCESS;
}

FZU2039 Pets 二分匹配,布布扣,bubuko.com

FZU2039 Pets 二分匹配

原文：http://blog.csdn.net/yitiaodacaidog/article/details/20228489