在线头像制作免费软件/自动seo系统

嗯...

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2063

 

这是一道很经典的匈牙利问题：

把男同学看成左边点，女同学看成右边点，如果两个同学愿意同坐过山车，则连边，最后输出最大匹配数即可...

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

int k, n, m;
int match[505], vis[505], g[505][505];

inline int dfs(int u){
    for(int i = 1; i <= m; i++){
        if(g[u][i] && !vis[i]){
            vis[i] = 1;
            if(!match[i] || dfs(match[i])){
                match[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

inline int hungary(){
    memset(match, 0, sizeof(match));
    int ans = 0;
    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main(){
    while(~scanf("%d%d%d", &k, &n, &m) && k != 0){
        memset(g, 0, sizeof(g)); 
        for(int i = 1; i <= k; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = 1;
        }
        printf("%d\n", hungary());
    }
    return 0;
}