二分匹配 专题整理

二分匹配学习记录

参考资料

二分图讲解及匈牙利模板

HDU 2444

题意

给出图，求是否二分图，和二分图的最大匹配数。

思路

二分图BFS染色+最大匹配。
染色方法就是从起点开始染色，如果上一个点是白色，相邻点就染为黑色。直到碰到矛盾处，就可以知道不是二分图。
最大匹配是通过遍历所有的点，递归更新匹配来扩展匹配。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 200+7;

bool maps[maxn][maxn];
int match[maxn], n, vis[maxn];

bool find(int i) { // 匈牙利算法 DFS
    for (int j = 1; j <= n; ++j)
    if (!vis[j] && maps[i][j]) {
        vis[j] = 1;
        if (!match[j] || find(match[j])) {
            match[j] = i;
            return 1;
        }
    }
    return 0;
}

bool isTwo() { // 二分图染色
    queue<int> q;
    memset(vis, 0, sizeof vis);
    q.push(1); vis[1] = 1;
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int j = 1; j <= n; ++j) {
            if (!maps[s][j]) continue;
            if (!vis[j]) {
                vis[s]==1?vis[j]=2:vis[j]=1;
                q.push(j);
            }
            else if (vis[j] == vis[s])
                return 0;
        }
    }
    return 1;
}

int main(){
    int m, ans, a, b;
    while (~scanf("%d%d", &n, &m)) {
        ans = 0;
        memset(maps, 0, sizeof maps);
        while (m--) {
            scanf("%d%d", &a, &b);
            maps[a][b] = maps[b][a] = 1;
        }
        if (n==1||!isTwo()) {
            printf("No\n"); continue;
        }
        memset(match, 0, sizeof match);
        for (int i = 1; i <= n; ++i) {
            memset(vis, 0, sizeof vis);
            ans += find(i);
        }
        printf("%d\n", ans/2);
    }
    return 0;
}

HDU 1083

题意

给出一个二分图，求是否能完全匹配。

思路

读入小坑。数组开小所以WA了两次。

之前的2444也算是匈牙利算法的基础版本，这个就是完全版了。都是用DFS过，但是BFS的匈牙利算法效率更高一些。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define LOCAL

const int maxn = 500+7;

vector<int> maps[maxn];
int p, n, match[maxn];
bool check[maxn];

int dfs(int u) {
    for (int i = 0; i < maps[u].size(); ++i) {
        int v = maps[u][i];
        if(check[v]) continue;
        check[v] = 1;
        if (match[v]==-1 || dfs(match[v])) {
            match[v] = u, match[u] = v;
            return 1;
        }
    }
    return 0;
}

int hungarian () {
    int rt = 0;
    memset(match, -1, sizeof match);
    for (int i = 1; i <= p; ++i) {
        memset(check, 0, sizeof check); // 增广路标记
        rt += dfs(i);
    }
    return rt;
}

void init(){
    scanf("%d%d", &p, &n);
    for (int i = 1; i <= p+n; ++i)
        maps[i].clear();
    for (int i = 1; i <= p; ++i) {
        int x, y; scanf("%d", &x);
        while (x--) {
            scanf("%d", &y);
            maps[i].push_back(p+y);
            maps[p+y].push_back(i);
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t;
    while (~scanf("%d", &t))
        while (t--) {
            init();
            hungarian() == p? puts("YES") : puts("NO");
        }
    return 0;
}