画圈游戏（匈牙利算法）

题意概述

有一个的方格图，有一些格子上面有星星，可以画圈，每个圈最多覆盖相邻两个格子，要覆盖每一个星星至少画几个圈

思路

1. 最好的情况：一个圈包含了两个星星---最大匹配
2. 然后就剩下了单个的孤寡星星，只能用单个圈覆盖
3. 假设有个最大匹配，一共个星星，一共需要个圈
4. 最小边覆盖 顶点数 最大匹配

代码

#include <bits/stdc++.h>

inline int read()
{
    int x = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            flag = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' || ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * flag;
}

// x + y为奇数放到左集合，为偶数放到右集合
// 为每一个左集合的星星匹配右集合的星星
// 代码实现注意细节
// 一维变二维
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
bool vis[42][42] = {0}; // vis[i][j] (i,j)点是否已经访问过
std::pair<int,int> Link[42][42]; // Link[i][j] (i, j)匹配的点是哪一个
char mat[42][42];
std::vector<std::pair<int, int>> left;
int n = 0, m = 0;
bool check(int x, int y)
{
    if ((x < 1) || (x > n) || (y < 1) || (y > m) || vis[x][y] || (mat[x][y] == 'o'))
    {
        return false;
    }
    return true;
}
bool dfs(int x, int y)
{
    int tx = 0, ty = 0, rx = 0, ry = 0;
    for (int i = 0; i < 4; i++)
    {
        tx = x + dir[i][0], ty = y + dir[i][1];
        if (check(tx, ty))
        {
            //std::cout << "tx = " << tx << " " << "ty = " << ty << "\n";
            rx = Link[tx][ty].first, ry = Link[tx][ty].second;
            vis[tx][ty] = 1;
            if ((rx == 0 && ry == 0) || dfs(rx, ry))
            {
                Link[tx][ty] = {x, y};
                return true;
            }
        }
    }
    return false;
}

int main()
{
    std::cin >> n >> m;
    char tmp;
    int x = 0, y = 0, s = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            std::cin >> tmp;
            mat[i][j] = tmp;
            if (tmp == '*')
            {
                s++;
                if ((i + j) & 1)
                {
                    left.push_back({i, j});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (int)left.size(); i++)
    {
        memset(vis, 0, sizeof(vis));
        x = left[i].first, y = left[i].second;
        if (dfs(x, y)) ans++;
    }
    // for (int i = 0; i < 10; i++)
    // {
    //     for (int j = 0; j < 10; j++)
    //     {
    //         int k = Link[i][j].first, p = Link[i][j].second;
    //         if (k != 0 || p != 0)
    //         {
    //             std::cout << i << "," << j << " -> " << k << "," << p << "\n";
    //         }
    //     }
    // }
    //std::cout << ans << "\n";
    std::cout << s - ans << "\n";
    return 0;
}