二分图

定义

结点由两个集合组成 两个集合内部没有边的图

也就是 存在一种方案 将结点划分成满足以上两个性质的集合

就是集合中的点都染成黑白 可以发现二分图中每条边都链接一个白点一个黑点

二分图不存在长为奇数的环（每条边都从一个集合走到另一个集合 偶数次才能回到同一个集合）

判断二分图：遍历：发现奇环就不是 否则是

二分图最大匹配

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

匈牙利算法（ntr算法哈哈

就是每次先配对 然后下一个人来配对的时候 遍历她所有可以访问的点 如果没被访问过并且没有配对 就配对 如果有配对了 就看看上一个人能不能让出来

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
int n, m, e;
const int N = 100010;
int vis[N], match[N];
struct Edge
{
    int v, ne;
} edge[N];
int head[N], idx;
void add(int a, int b)
{
    edge[++idx] = {b, head[a]};
    head[a] = idx;
}

bool dfs(int u)
{
    for (int i = head[u]; i; i = edge[i].ne)
    {
        int v = edge[i].v;
        if (vis[v])
            continue;
        vis[v] = 1;
        if (!match[v] || dfs(match[v]))
        {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;

    cin >> n >> m >> e;
    for (int i = 0; i < e; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            ans++;
    }
    cout << ans;

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

xmuoj | AI2024春《算法设计与分析》第三次上机

棋盘覆盖问题 可以当作二分图来写：

这样思考 每个块都把他当作是两个点合在一起 假设中间是一个白点 （2，2）那么（1，2）（2，1）（3，2）（2，3）都是黑点 然后建边 这样就类似与上面的二分图了 对白点或者黑点进行二分图查找就可以找到最大匹配（一个匹配就相当于是放了一块木板）

难点在于想到用二分图的做法来做这个题 还有怎样去建边

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/

const int N = 110;//N开太大会超时
int b[N][N], vis[N * N], match[N * N];// N*N才能过 不然数组太小
vector<int> e[N * N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int ans = 0;
// 匈牙利算法
bool bfs(int u)
{
    for (auto v : e[u])
    {
        if (vis[v])
            continue;
        vis[v] = 1;
        if (!match[v] || bfs(match[v]))
        {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int n, t;
    cin >> n >> t;

    for (int i = 0; i < t; i++)
    {
        int x, y;
        cin >> x >> y;
        b[x][y] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!b[i][j])
            {
                for (int k = 0; k < 4; k++)
                {
                    int x = dx[k] + i, y = dy[k] + j;
                    if (x >= 1 && x <= n && y >= 1 && y <= n && !b[x][y])
                    {
                        // 建边
                        e[i * n + j].push_back(x * n + y);
                        e[x * n + y].push_back(i * n + j);
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if ((i ^ j) & 1) // 枚举奇数结点
                continue;
            memset(vis, 0, sizeof(vis));//清空
            if (bfs(i * n + j))
                ans++;
        }
    }
    cout << ans;
    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}