过山车
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3105 Accepted Submission(s): 1298
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
最简单的二分图,也是我第一次写的二分图,第一次做有些困难,以后做就不那么难了。二分图我个人理解是:逐个逐个匹配,若那个人被匹配了,则找匹配那个的人看看能不能找其他人匹配,不断地找,好像这些叫做增广路,定义还没怎么看,先做了些简单题。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int N = 505;
bool map[N][N], flag[N];
int pre[N];
int n, m, num;
//匈牙利算法(二分匹配)
int find(int cur) //cur为当前女生
{
int i;
for(i = 1; i <= m; i++) //被匹配的男生
{
if(map[cur][i] && !flag[i]) //该男生未被匹配
{
flag[i] = true; //这次匹配中,标记该男生已匹配
if(pre[i] == -1 || find(pre[i]))//该男生没有被女生匹配 or 该女生继续找其他男生 -> ok
{
pre[i] = cur; //男生[i]属于女生cur
return 1;
}
}
}
return 0;
}
int main()
{
int i, girl, boy, sum;
while(scanf("%d", &num), num)
{
scanf("%d %d", &n, &m); //n是女生数量,m是男生数量
memset(map, false, sizeof(map));
memset(pre, -1, sizeof(pre));
for(i = 0; i < num; i++)
{
scanf("%d %d", &girl, &boy);
map[girl][boy] = true; //可以匹配
}
sum = 0;
for(i = 1; i <= n; i++) //女生去匹配男生
{
memset(flag, 0, sizeof(flag)); //每次重新标记0
sum += find(i);
}
printf("%d\n", sum);
}
return 0;
}
分享到:
相关推荐
二分图的完美匹配是指在一个图中,每个顶点恰好被一条边连接,使得图中的所有顶点都被连接且没有多余未使用的边。在实际应用中,二分图的完美匹配常常出现在分配问题、调度问题等领域。KM算法,即Kuhn-Munkres算法,...
**匹配**:在一个二分图\( G \)中,存在一个子图\( G' \),若\( G' \)的边集中任意两条边不共用同一个顶点,则称\( G' \)的边集为\( G \)的一个匹配。 **最大匹配**:在所有可能的匹配中,包含边数最多的匹配被称为...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
1. "2013暑期多校联合训练第一场0723-解题报告.pdf":这个PDF文件包含了这次训练的解题报告,可能包括了所有题目及其解法的详细分析,对于参赛者来说,这是理解和学习解题策略的重要资源。 2. "2013暑期多校联合训练...
【标题】"2017hdu多校联合训练第一场标程及数据"涉及到的是一个编程竞赛的资源集合,主要是针对ACM(国际大学生程序设计竞赛)的比赛训练。这个标题意味着这个压缩包包含了该赛事的官方解决方案(标程)以及用于测试...
HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案。这里的“java实现”意味着作者使用Java作为编程工具来解答这些算法题。 在Java编程方面,以下是一些可能涵盖的知识点: 1. ...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
具体地,题目涉及到了斐波那契数列的一个变种:F(1)=1, F(2)=1, F(3)=1, F(4)=1, F(n>4)=F(n-1)+F(n-2)+F(n-3)+F(n-4),其中n > 4。这里的关键是要能够计算出F(n)的值,而由于这个序列的增长速度非常快,传统的整数...
例如,一个简单的动态规划问题可以是“斐波那契数列”,其中状态通常定义为第n个斐波那契数,状态转移方程为F(n) = F(n-1) + F(n-2),初始条件为F(0) = 0,F(1) = 1。 在HDU的DP题目中,可能会有各种复杂度的题目,...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。...ACM HDU 题目分类是一个非常重要的参考资源,对于编程选手来说,掌握这些分类可以帮助他们更好地理解和解决问题。
如果整个图都可以按照这种方式进行着色,那么该图就是一个二分图。 - **实现代码**: ```cpp booldfs(int u, int key){ col[u] = key; for(int i = 0; i [u].size(); ++i){ int v = g[u][i]; if(col[v] == ...
最后,输出压缩后的矩阵的第一列第一个元素,作为结果。 4. HDU 1170 - 算术运算 这个问题看起来是不完整的,因为最后一段代码没有给出具体的实现。通常这类问题会要求处理算术表达式,可能涉及到操作符优先级、...
HDU ACM培训资料是一系列专为参与ACM(国际大学生程序设计竞赛)的学员准备的教育资源,涵盖了算法和编程竞赛的核心知识。这份压缩包包含了11个不同主题的课时,旨在帮助学员全面掌握ACM竞赛所需的技能。下面将详细...
此题目要求输入一个特定日期(格式为“年/月/日”),然后计算并输出这一天是一年中的第几天。例如,输入“2023/1/1”,则应该输出“1”。 ### 解题思路 1. **判断平年与闰年**:首先需要判断输入的年份是否为闰年...
**第一步:线分割平面** 首先解决较为简单的二维情况,即如何用 _n_ 条直线分割一个平面,并求出最多可以将平面分割成多少部分。这里的关键在于理解每新增一条直线都会增加新的分割区域数。 - 对于第 _1_ 条直线,...
【标题】"2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程).zip" 提供的是一个编程竞赛的数据集和参考解决方案,源自2019年的一场多所大学联合举办的训练比赛。这样的资源对于参与ACM(国际...
HDU1059的代码
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu1001解题报告