题目链接

洛谷P3386

题目分析

本题所用算法为匈牙利算法
主要思想就是当有两个左部点对应的右部点冲突时,就让之前的那个左部点点去匹配与他相连的其他的右部点,如果匹配成功了,那么第一个左部点就可以让出原配来给第二个匹配,否则不让。

题目代码

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, m, e;
int mp[N][N], book[N], match[N];

bool dfs(int u) {
    for (int i = 1; i <= m; i++) {
        if (mp[u][i] && !book[i]) {
            book[i] = 1;
            if (!match[i] || dfs(match[i])) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
#ifndef ONLINE_JUDGE    
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++) {
        int a, b;
        cin >> a >> b;
        mp[a][b] = 1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        memset(book, 0, sizeof book);
        if (dfs(i)) sum++;
    }
    cout << sum << endl;

    return 0;
}
最后修改:2021 年 03 月 30 日 10 : 16 AM