过山车
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3075 Accepted Submission(s): 1287
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
3
Author
PrincessSnow
#include <iostream>
using namespace std;
const int MAX = 505;
bool G[MAX][MAX]; //存路径,存在的话设为true,否则为false
bool flag[MAX]; //标志每次查找,此点是否已经被匹配过
int mark[MAX]; //记下右边的被左边的那个点匹配
int k, m, n;
//算法思路:二分匹配,匈牙利算法
bool dfs(int x)
{
int i;
for(i = 1; i <= n; i++)
{
if(!G[x][i] || flag[i])
continue;
flag[i] = true;
if(!mark[i] || dfs(mark[i]))
{
mark[i] = x;
return true;
}
}
return false;
}
int main()
{
int i, a, b, count;
while(cin>>k, k)
{
count = 0;
cin>>m>>n;
memset(G, false, sizeof(G));
for(i = 1; i <= k; i++)
{
cin>>a>>b;
G[a][b] = true;
}
memset(mark, 0, sizeof(mark));
for(i = 1; i <= m; i++)
{
memset(flag, false, sizeof(flag));
if(dfs(i))
count++;
}
cout<<count<<endl;
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
自己做的HDU ACM已经AC的题目
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU图论题目分类
hdu 1005.比较简单的一道题,有兴趣的可以看看。