过山车匈牙利算法二分图最大匹配

迈不过友情╰ 2024-01-15 06:42 153阅读 0赞

## 过山车 ##

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 33174 Accepted Submission(s): 14197**

**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**

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

**Sample Output**

**Author**

PrincessSnow

**Source**

[RPG专场练习赛][RPG]

**Recommend**

lcy | We have carefully selected several similar problems for you: [1068][] [1083][] [2444][] [1281][] [1150][]

不懂匈牙利算法的可以看这个：[https://blog.csdn.net/dark\_scope/article/details/8880547][https_blog.csdn.net_dark_scope_article_details_8880547]

讲的非常nice！

这道题我遇到的问题是：题上说：女生Ai愿意和男生Bj做partner，女生人数为M,男生人数为N，应该遍历女生，

#include<stdio.h>
    #include<string.h>
    #define range 505
    int line[range][range];
    int used[range];
    int girl[range];
    int n,m,k,sum=0;
    int find(int s)
    {
    	int i,j;
    	for(i=1;i<=n;i++)                   //女追男，而非男追女。 
    	{
    		if(line[s][i]&&used[i]==0)
    		{
    			used[i]=1;
    			if(girl[i]==0||find(girl[i]))
    			{
    				girl[i]=s;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    int main(){
    	int i,j,a,b;
    	while(~scanf("%d",&k))
    	{
    		if(k==0)
    		break;
    		scanf("%d %d",&m,&n);
    		memset(line,0,sizeof(line));
    		memset(girl,0,sizeof(girl));
    		
    		for(i=0;i<k;i++)
    		{
    			scanf("%d %d",&a,&b);
    			line[a][b]=1;
    		}
    		for(i=1;i<=m;i++)          // 这个地方要注意啦，先遍历女生。 
    		{ 
    			memset(used,0,sizeof(used));
    			if(find(i))
    			sum++;
    		}
    		printf("%d\n",sum);
    		sum=0;
    	}
    	return 0;
    }

加油，不要荒废青春。

[RPG]: http://acm.hdu.edu.cn/search.php?field=problem&key=RPG%D7%A8%B3%A1%C1%B7%CF%B0%C8%FC&source=1&searchmode=source
[1068]: http://acm.hdu.edu.cn/showproblem.php?pid=1068
[1083]: http://acm.hdu.edu.cn/showproblem.php?pid=1083
[2444]: http://acm.hdu.edu.cn/showproblem.php?pid=2444
[1281]: http://acm.hdu.edu.cn/showproblem.php?pid=1281
[1150]: http://acm.hdu.edu.cn/showproblem.php?pid=1150
[https_blog.csdn.net_dark_scope_article_details_8880547]: https://blog.csdn.net/dark_scope/article/details/8880547