二分匹配学习记录

参考资料

二分图讲解及匈牙利模板

HDU 2444

The Accomodation of Students

题意

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

思路

二分图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

Courses

题意

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

思路

读入小坑。数组开小所以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;
}

HDU 1281

棋盘游戏

题意

给出一个不规则棋盘,问能放下几个车,让他们互相不能攻击?这种情况下,如果某个放车的地方改为不可放置,这时结果发生了变化,就称之为重要点。问有几个重要点?

思路

二分匹配。将行和列分别看成二分图的左点和右点,最大匹配就是能放下多少车。

代码

#include <bits/stdc++.h>
using namespace std;
#define LOCAL

const int maxn = 100+7;

int maps[maxn][maxn*2];
int n, m, k, match[maxn*2];
bool check[maxn*2];
struct node {
    int a, b;
    node(int _a, int _b) {
        a = _a, b = _b;
    }
};
vector<node> pairs;

int dfs(int u) {
    for (int i = n+1; i <= n+m; ++i) {
        if (!maps[u][i]) continue;
        int v = 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 <= n; ++i) {
        memset(check, 0, sizeof check); // 增广路标记
        rt += dfs(i);
    }
    return rt;
}

void init(){
    memset(maps, 0, sizeof maps);
    while (k--) {
        int a, b; scanf ("%d%d", &a, &b);
        maps[a][n+b] = 1;
    }
    pairs.clear();
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int cas = 0;
    while (~scanf("%d%d%d", &n, &m, &k)) {
        init();
        int ans = hungarian();
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (match[i]) pairs.push_back(node(i, match[i]));
        for (int i = 0; i < pairs.size(); ++i) {
            int u = pairs[i].a, v = pairs[i].b;
            maps[u][v] = 0;
            int m = hungarian();
            maps[u][v] = 1;
            if (m != ans) ++cnt;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n", ++cas, cnt, ans);
    }
    return 0;
}

HDU 2819

题意

给出一个01矩阵,问能否通过交换列使其主对角线上都为1。

思路

依然是把行和列看做左右点集,通过行列二分匹配得到完全匹配。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100+7;

int maps[maxn][maxn*2], n, match[maxn*2];
bool check[maxn*2];
struct node {
    int a, b;
    node(int _a, int _b) {
        a = _a, b = _b;
    }
};

int dfs(int u) {
    for (int i = n+1; i <= n*2; ++i) {
        if (!maps[u][i] || check[i]) continue;
        check[i] = 1;
        if (match[i]==-1 || dfs(match[i])) {
            match[i] = u, match[u] = i;
            return 1;
        }
    }
    return 0;
}

int hungarian() {
    int rt = 0;
    memset(match, -1, sizeof match);
    for (int i = 1; i <= n; ++i) {
        memset(check, 0, sizeof check);
        rt += dfs(i);
    }
    return rt;
}

void init() {
    memset(maps, 0, sizeof maps);
    for (int i = 1; i <= n; ++i)
        for (int j = n+1; j <= n*2; ++j)
            scanf("%d", maps[i]+j);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    while (~scanf("%d", &n)) {
        init();
        int ans = hungarian();
        if (ans != n) {
            puts("-1");
            continue;
        }
        vector<node> op;
        for (int i = 1; i <= n; ++i) {
            if (match[i] == i) continue;
            for (int j = n+i+1; j <= n*2; ++j){
                if (match[j] == i) {
                    match[j] = match[i];
                    op.push_back(node(i, match[i]-n));
                }
            }
        }
        printf("%d\n", op.size());
        for (int i = 0; i < op.size(); ++i)
            printf("R %d %d\n", op[i].a, op[i].b);
    }
    return 0;
}