首页 > 其他 > 详细

TOJ 3635 过山车

时间:2014-02-19 00:46:58      阅读:395      评论:0      收藏:0      [点我收藏+]

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

Source

HDOJ

 

二分图匹配,匈牙利算法。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <string.h>
#define MAXN 520
 
bool bmap[MAXN][MAXN];
bool bmask[MAXN];
 
int K,M,N;
int cx[MAXN];
int cy[MAXN];
 
int findpath(int u){
    for(int i=1; i<=N; i++){
        if(bmap[u][i]&& !bmask[i]){
            bmask[i]=1;
            if(cy[i]==-1 || findpath(cy[i])){
                cy[i]=u;
                cx[u]=i;
                return 1;
            }
        }
    }
    return 0;
}
 
int maxMatch(){
    int res=0;
    memset(cx,-1,sizeof(cx));
    memset(cy,-1,sizeof(cy));
    for(int i=1; i<=M; i++){
        if(cx[i]==-1){
            memset(bmask,0,sizeof(bmask));
            res+=findpath(i);
        }
    }
    return res;    
}
 
int main(int argc, char *argv[])
{
    while( scanf("%d",&K), K!=0 ){
        scanf("%d %d",&M ,&N);
        memset(bmap,0,sizeof(bmap));
        int u,v;
        while(K--){
            scanf("%d %d",&u ,&v);
            bmap[u][v]=1;
        }
        int ans=maxMatch();
        printf("%d\n",ans);
    }
    return 0;
}

TOJ 3635 过山车

原文:http://www.cnblogs.com/chenjianxiang/p/3554201.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!