过山车

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 9745 Accepted Submission(s): 4294

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

又是一个简单直接的二分匹配问题。

。今天刚刚学。。

也就先找找简单练手。。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int M = 1000 + 5;

int k, m, n;

int link[M];

bool MAP[M][M];

bool cover[M];

int ans;

void init()

{

    int x, y;

    memset(MAP, false, sizeof(MAP));

    scanf("%d%d", &m, &n);

    for(int i=1; i<=k; i++)

    {

        scanf("%d%d", &x, &y);

        MAP[x][y]=true;

    }

}

bool dfs(int x)

{

    for(int y=1; y<=n; y++)

    {

        if(MAP[x][y] && !cover[y])

        {

            cover[y]=true;

            if(!link[y] || dfs(link[y]))

            {

                link[y]=x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    while(scanf("%d", &k) && k)

    {

        ans=0;

        init();

        memset(link, false, sizeof(link));

        for(int i=1; i<=m; i++)

        {

            memset(cover, 0, sizeof(cover));

            if( dfs(i) )

                ans++;

        }

        printf("%d\n", ans);

    }

    return 0;

}

秒客网

HDU 2063：过山车（偶匹配，匈牙利算法）

过山车

相关文章