Talk is Cheap, Show Me the Code!

0%

过山车

Posted on In

给定n个男生和m个女生，坐过山车。过山车每排只有两个位置，且只能是一男一女。已经一些想坐在一起的意愿。
求最多可以坐多少排？

输入描述:

输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。K<=1000。
N, M<=500.接下来的K行，每行有两个数，分别表示女生A_i愿意和男生B_j坐一起。最后一个0结束输入。

输出描述:

对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。

示例1
输入

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

输出

3

guoshanche.cppview raw
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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int mp[N][N];
int st[N];
int a[N], b[N];
int n,m;
int ans;

bool sp(int v){
    for(int i=1;i<=m;i++){
        if(mp[v][i] && !st[i]){
            st[i] = 1; //类似于减枝
            if(b[i]==-1 || sp(b[i])){
                b[i] = v;
                a[v] = i;
                return true;
            }
        }
    }
    return false;
}

void solve(){
    ans = 0;
    memset(a, -1, sizeof a);
    memset(b, -1, sizeof b);
    for(int i=1;i<=n;i++){
        if(a[i]==-1){
            memset(st, 0, sizeof st); //对每一i，都要做一次
            if(sp(i)) ans ++;
        }
    }
}
int main(){
    int k;
    while(scanf("%d", &k) && k){
        scanf("%d%d", &n, &m);
        int a, b;
        memset(mp, 0, sizeof mp);
        while(k--){
            scanf("%d%d", &a, &b);
            mp[a][b] = 1;
        }
        solve();
        printf("%d\n", ans);
    }
    return 0;
}