二分图最大匹配

题意：

分析：

经典的求最大子集的问题。我们先求最大匹配。最大子集 = 总定点数 - 最大匹配
选择你的算法，我选择HK算法！

但是摆在我们面前的还有一个问题：如何区分图中顶点所在的集合？

1.染色法：
我们连完边建完图后，进行搜索，搜索深度为奇数的为一个子集，为偶数的为一个子集

2.观察法：
对，我们不妨先在草稿纸上画画：

这是我画的，我们很容易就发现当i+j为奇数是是一个子集，为偶数时是另一个子集。
如此我们找到了划分的一句。接下来划分就可以了。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
pair<int, int> pii;
const int max_n = 330;
int n;
const int inf = 2e9;
char M[max_n][max_n];
int map[max_n][max_n];
vector<int> G[max_n * max_n];
int dir[8][2] = { {-2,-1},{-2,1},{-1,-2},{-1,2},{1,2},{1,-2},{2,1},{2,-1} };
int rightTo[max_n * max_n];
int leftTo[max_n * max_n];
int distright[max_n * max_n];
int distleft[max_n * max_n];
int dist;
int tot1, tot2;
bool searchpath() {
    fill(distright, distright + tot1 + 1, -1);
    fill(distleft, distleft + 1 + tot2, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= tot1;i++) {
        if (rightTo[i] == -1) {
            que.push(i);
            distright[i] = 0;
        }
    }
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distright[u] > dist)break;
        for (int i = 0;i < G[u].size();i++) {
            int v = G[u][i];
            if (distleft[v] != -1)continue;
            distleft[v] = distright[u] + 1;
            if (leftTo[v] == -1)dist = distleft[v];
            else {
                distright[leftTo[v]] = distleft[v] + 1;
                que.push(leftTo[v]);
            }
        }
    }return dist != inf;
}

bool matchpath(int x) {
    for (int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        if (distleft[v] != distright[x] + 1)continue;
        if (distleft[v] == dist && leftTo[v] != -1)continue;
        distleft[v] = -1;
        if (leftTo[v] == -1 || matchpath(leftTo[v])) {
            leftTo[v] = x;rightTo[x] = v;
            return true;
        }
    }return false;
}

int HK() {
    fill(rightTo, rightTo + tot1 + 1, -1);
    fill(leftTo, leftTo + tot2 + 1, -1);
    int ans = 0;
    while (searchpath()) {
        for (int i = 1;i <= tot1;i++) {
            if (rightTo[i] == -1 && matchpath(i))
                ans++;
        }
    }return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            cin >> M[i][j];
    tot1 = tot2 = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (M[i][j] == '1')continue;
            if (i + j & 1)map[i][j] = ++tot2;
            else map[i][j] = ++tot1;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (M[i][j] == '1')continue;
            if (!((i + j) & 1)) {
                for (int k = 0;k < 8;k++) {
                    int x = i + dir[k][0];
                    int y = j + dir[k][1];
                    if (x<1 || y<1 || x>n || y>n || M[x][y] == '1')continue;
                    G[map[i][j]].push_back(map[x][y]);
                }
            }
        }
    }
    cout << tot1 + tot2 - HK() << endl;
}