HDU 2063 过山车 (匈牙利算法)

题目链接：HDU 2063

Problem Description

Input

Output

Sample Input

6 3 3

1 1

1 2

1 3

2 1

2 3

3 1

0

Sample Output

3

Source

Solution

题意

如题。

思路

二分图最大匹配。

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

Code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;

int n, m;

int g[maxn][maxn];

int vis[maxn], ok[maxn];

bool dfs(int x) {

    for(int i = 1; i <= n; ++i) {

        if(!vis[i] && g[x][i]) {

            vis[i] = 1;

            if(!ok[i] || dfs(ok[i])) {

                ok[i] = x;

                return true;

            }

        }

    }

    return false;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k;

    while(cin >> k && k) {

        cin >> m >> n;

        memset(g, 0, sizeof(g));

        memset(ok, 0, sizeof(ok));

        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;

}