HDU/HDOJ 2063 过山车（二分图最大匹配，vector的使用）

本文主要是介绍HDU/HDOJ 2063 过山车（二分图最大匹配，vector的使用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.split.hdu.edu.cn/showproblem.php?pid=2063

过山车

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18847 Accepted Submission(s): 8230

Problem Description

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

Input

输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

Output

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

Sample Input

Sample Output

Author

PrincessSnow

Source

RPG专场练习赛

题意：

裸裸地二分图模板，上次敲匈牙利是什么时候都不记得了......

二维数组的模板都差点忘记了！

第二次使用 vector ，宇神说很强大的一个容器。童鞋也不会 vector ? 点击这里参考学下！

问题卡在如下：

for(int j=0; j<=Vec[gril].size(); j++) {//遍历男生

应该是

j<Vec[gril].size()

最基础的都被忽略了，也怪自己有点懒，直接修改的是二维数组的代码！

Code：vector 实现

降低空间复杂度

#include<stdio.h>
#include<cstring>
#include<vector>
using namespace std;
const int MYDD=1103;
const int MAXN=512;vector<int> Vec[MYDD];//创建一个容器 
int Link[MYDD];//记录和当前男生 j 在一起的女生 Link[j]
bool Vis[MYDD];//记录男生 j 已经有无伙伴的状态bool HK(int gril) {for(int j=0; j<Vec[gril].size(); j++) {//遍历该女生要求的男生int v=Vec[gril][j];if(!Vis[v]) {Vis[v]=true;if(Link[v]==-1||HK(Link[v])) {// *wa_bug HK(v)Link[v]=gril;//当前女生和男生 j 在一组return true;}}}return false;
}int main() {int k;while(scanf("%d",&k)&&k) {int m,n;scanf("%d%d",&m,&n);for(int j=0; j<MAXN; j++)Vec[j].clear();//容器的清空即初始化for(int j=0; j<k; j++) {int gril,boy;scanf("%d%d",&gril,&boy);Vec[gril].push_back(boy);//gril 尾部加入一个中意的 boy}/***匈牙利算法****/int ans=0;memset(Link,-1,sizeof(Link));for(int j=1; j<=m; j++) {//遍历女生memset(Vis,false,sizeof(Vis));if(HK(j))	ans++;}printf("%d\n",ans);}return 0;
}

Code：二维数组实现

#include<stdio.h>
#include<cstring>
const int MYDD=1103;
const int MAXN=512;bool Map[MAXN][MAXN];//记录女生 i和男生 j 在一组
int Link[MYDD];//记录和当前男生 j 在一起的女生 Link[j]
bool Vis[MYDD];//记录男生 j 的伙伴状态bool HK(int gril,int n) {for(int i=1; i<=n; i++) {//遍历男生if(!Vis[i]&&Map[gril][i]) {Vis[i]=true;if(Link[i]==-1||HK(Link[i],n)) {Link[i]=gril;//当前女生和男生 i 在一组return true;}}}return false;
}int main() {int k;while(scanf("%d",&k)&&k) {int m,n;scanf("%d%d",&m,&n);memset(Map,false,sizeof(Map));for(int j=0; j<k; j++) {int gril,boy;scanf("%d%d",&gril,&boy);Map[gril][boy]=true;}/***匈牙利算法****/int ans=0;memset(Link,-1,sizeof(Link));for(int j=1; j<=m; j++) {//遍历女生memset(Vis,false,sizeof(Vis));// *wa_bug 不能够使用 if(Link[j]==-1)if(HK(j,n))	ans++;}printf("%d\n",ans);}return 0;
}
/* By : Shyazhut */

这篇关于HDU/HDOJ 2063 过山车（二分图最大匹配，vector的使用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！