HDU 2063 过山车 匈牙利算法

本菜鸡终于自己走了一遍，感觉很妙，但是总觉得自己想的话想不到这个递归结构。
还是太菜了。要多练练递归（感觉还是会想不到

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
//腾 
int n, m;//男生 女生 
int g[N][N];//graph 描述图关系 
int vis[N], boy[N];

bool dfs(int x) { 
    for(int i = 1; i <= n; i++) {//遍历每个男生 
        if(!vis[i] && g[x][i]) {//如果存在关系且没有被访问过 
            vis[i] = 1;//访问记录 
            if(!boy[i] || dfs(boy[i])) {//如果男生名花无主或者可以挪动 
                boy[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int k;
    while(cin >> k && k) {
        cin >> m >> n;
        memset(g, 0, sizeof(g));
        memset(boy, 0, sizeof(boy));
        for(int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            g[a][b] = 1;
        }
        int sum = 0;
        for(int i = 1; i <= m; i++) {//遍历每一个女生 
            memset(vis, 0, sizeof(vis));//每一个女生都清空访问记录 
            if(dfs(i)) sum++;
        }
        cout << sum << endl;
    }
    return 0;
}

补充WuTao大佬的话，以后来看：
二分图最大匹配。

可以用最大流解决。也可以用匈牙利算法。匈牙利算法是最大流方法的一种优化。若采用邻接矩阵存图，时间复杂度 O(V2)，空间复杂度 O(V2)。若采用邻接表，时间复杂度 O(VE)，空间复杂度 O(V+E)。