HDOJ 过山车

今天刚学完二分图匹配算法写个博客分享一下

 

 

题目如下

 

RPG girls今天和大家一起去比赛玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生但是，每个女孩都有各自的想法，举个例子把，兔子只愿意和XHD或PQK做伙伴，草只愿意和linle或LL做伙伴，PrincessSnow愿意和水域浪子或伪考虑到费用问题，老板刘决定只让找到合伙人的人去坐过山车，其他的人，嘿嘿，就站在旁边看着吧。聪明的Acmer，你可以帮忙忙算算最多有多少对组合可以坐上过山车吗？  

 

输入 0 <K <= 1000
1 <= N和M <= 500。接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。  

 

输出 对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。  

 

样本输入

6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0  

 

样本输出

3  

 

作者

雪公主  

 

来源

RPG专场练习赛                                       明显的二分图用匈牙利算法很容易解决 代码实现如下      

#include<bits/stdc++.h>
using namespace std;
#define M 507
int n,m,k;
int Map[M][M];   //标记男女是否满足条件
int link[M];     //储存女生当前的对象是谁
int usd[M];      //判断女生是否有对象
int dfs(int u) //用dfs来实现查找，u代表的是男生
{
    int v;      //v代表女生
    for(v=1;v<=m;v++)
	{
		if(Map[u][v]&&!usd[v])//判断男女是否满足条件，而且女生当前这轮是否已经有对象
		{
			usd[v]=1;   //表示这个女生现在被u这个男生所选，后面帮v这个女生前男友找新女友的时候就不再考虑v；
			if(link[v]==-1||dfs(link[v]))//link【v】==-1 标识女生没有男朋友，dfs（link【v】）表示如果女生的前男友能找到新女友
			{
			   link[v]=u;        //储存当前男友
			   return 1;         //返回真，一会用于判断最大匹配数是否加一
			}
		}
	}
    return 0;
}
int main()
{
	while(cin>>k)
	{
		memset(Map,0,sizeof(Map));//初始化Map为0
		memset(link,-1,sizeof(link));//初始化link为-1
		if(k==0)break;
		cin>>n>>m;
		while(k--)
		{
			int x,y;
			cin>>x>>y;
			Map[x][y]=1;//标记男女
		}
		int ans=0;
		for(int u=1;u<=n;u++)
		{
			memset(usd,0,sizeof(usd));//usd要在每趟为新u找对象时初始化，因为如果不初始化usd新的u就不会和有对象的v配对
			if(dfs(u))ans++;
		}
		cout<<ans<<endl;
	}
}