acwing算法提高之图论--二分图

1 介绍

本专题用来记录二分图的题目。

以下条件互相等价：

1. 一个图是二分图。
2. 染色法过程中不存在矛盾。
3. 图中不存在奇数环。

二分图本质上是一个无向图的问题！

结论：
最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖

2 训练

题目1：257关押罪犯

C++代码如下，

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 20010;
int n, m;
vector<vector<PII>> g(N);
int color[N];

bool dfs(int a, int c, int mid) {
    color[a] = c;
    
    //看结点a能走到哪儿
    for (auto [b, w] : g[a]) {
        if (w <= mid) continue; 
        if (!color[b] && !dfs(b, 3 - c, mid)) return false;
        if (color[b] && color[b] == c) return false;
    }
    return true;
}

bool check(int mid) {
    memset(color, 0, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; ++i) {
        if (!color[i] && !dfs(i, 1, mid)) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main() {
    cin >> n >> m;
    int a, b, w;
    while (m--) {
        cin >> a >> b >> w;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }
    
    int l = 0, r = 1e9;
    int res = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

题目2：372棋盘覆盖

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool find(int x, int y) {
    for (int i = 0; i < 4; ++i) {
        int a = x + dx[i], b = y + dy[i];
        if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b]) {
            st[a][b] = true;
            PII t = match[a][b];
            if (t.x == -1 || find(t.x, t.y)) {
                match[a][b] = {x, y};
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    
    while (m--) {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }
    
    memset(match, -1, sizeof match);
    
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if ((i + j) % 2 && !g[i][j]) {
                memset(st, 0, sizeof st);
                if (find(i, j)) res++;
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

题目3：376机器任务

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, k;
int match[N];
bool g[N][N], st[N];

bool find(int x) {
    for (int i = 0; i < m; ++i) {
        if (!st[i] && g[x][i]) {
            st[i] = true;
            if (match[i] == -1 || find(match[i])) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    while (cin >> n, n) {
        cin >> m >> k;
        memset(g, 0, sizeof g);
        memset(match, -1, sizeof match);
        
        while (k--) {
            int t, a, b;
            cin >> t >> a >> b;
            if (!a || !b) continue;
            g[a][b] = true;
        }
        
        int res = 0;
        for (int i = 0; i < n; ++i) {
            memset(st, 0, sizeof st);
            if (find(i)) res++;
        }
        
        cout << res << endl;
    }
    
    return 0;
}

题目4：378骑士放置

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (g[a][b]) continue;
        if (st[a][b]) continue;
        
        st[a][b] = true;
        
        PII t = match[a][b];
        if (t.x == 0 || find(t.x, t.y)) {
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k;
    
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] || (i + j) % 2) continue;
            memset(st, 0, sizeof st);
            if (find(i, j)) res++;
        }
    }
    
    cout << n * m - k - res << endl;
    
    return 0;
}

题目5：379捉迷藏

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N], st[N];
int match[N];

bool find(int x) {
    for (int i = 1; i <= n; ++i) {
        if (d[x][i] && !st[i]) {
            st[i] = true;
            int t = match[i];
            if (t == 0 || find(t)) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }
    
    //传递闭包
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] |= d[i][k] & d[k][j];
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        memset(st, 0, sizeof st);
        if (find(i)) res++;
    }
    
    printf("%d\n", n - res);
    
    return 0;
}

3 参考

染色法判断二分图
匈牙利算法求最大匹配