首页 / 算法 / hdu 2063 给男女匹配 (匈牙利算法）

hdu 2063 给男女匹配 (匈牙利算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了hdu 2063 给男女匹配 (匈牙利算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1056字，纯文字阅读大概需要2分钟。

内容图文

来源：http://acm.hdu.edu.cn/showproblem.php?pid=2063 

题意：

有k个组合a,b组合，代表a愿意与b坐过山车，共m个女生 n个男生，问有多少个满意的匹配

题解：

这是一道匈牙利算法的裸题，用递归询问是否能安排好某个女生，如果能就ans++

注意，在同一回合的询问中，某个女生只寻找一次其它男生，第二次寻找时一定无法找到，直接返回0就行

这是我第二次做这道题，在前几个月已经做过，没想到这就是传说中的二分图  Orz

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 500+5;

int part[maxn];
bool vi[maxn];
int n,m,k;

vector<int>ma[maxn];

bool is_ok(int x)
{
	 if(vi[x]==0)vi[x]=1;
	 else return 0;
     for(int i=0;i<ma[x].size();i++)
	 {
          if(part[ma[x][i]]==0||is_ok(part[ma[x][i]]))
		  {
			  part[ma[x][i]]=x;
			  return 1;
		  }
	 }
	 return 0;
}

int main()
{
    while(scanf("%d",&k)!=EOF)
	{
		  if(k==0)break;
		  scanf("%d %d",&m,&n);
		  int ans=0;
		  for(int i=1;i<maxn;i++)
		  {
			  ma[i].clear();
			  part[i]=0;
		  }
  	      for(int i=1;i<=k;i++)
		  {
			  int a,b;
 			   scanf("%d %d",&a,&b);
			   ma[a].push_back(b);
		  }
		  for(int i=1;i<=m;i++)
		  {
			   for(int j=1;j<=m;j++)vi[j]=0;
               if(is_ok(i))
      			   ans++;
		  }
		  printf("%d\n",ans);
	}
	return 0;
}

原文：https://www.cnblogs.com/carcar/p/9079442.html

内容总结

以上是互联网集市为您收集整理的hdu 2063 给男女匹配 (匈牙利算法）全部内容，希望文章能够帮你解决hdu 2063 给男女匹配 (匈牙利算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1228052.html

来源：【匿名】