棋盘游戏

增广路

这道题，关键就是让我们判断。二分图匹配时，有哪些边是必须被用上的。
一个简单朴素的思想就是：我们枚举边，删除这条边后在求其最大匹配数。看是否减少了。
能过，但是复杂度其实是极高的。
那我们想一想是否可以优化这个算法？
事实上就是增广路的思想。我们删除这条边后，不需要再从头开始求最大匹配数。
而是，我们可以在就已经匹配的基础上，再去尝试寻找一条增广路。看能不能找到。
能找到就说明，这条边不是必须的。不能找到就说明这条边是必须的。
复杂度一下子就降下来了。

代码如下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int max_n = 110;
const int max_m = 1e4 + 100;
const int inf = 2e9;
struct edge{
    int to, next;
    bool vis;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, bool vis = true) {
    E[cnt].to = to;E[cnt].next = head[from];
    E[cnt].vis = vis;head[from] = cnt++;
}

int leftTo[max_n], rightTo[max_n];
int distleft[max_n], distright[max_n];
int dist;
bool seacherpath(int left_tot, int right_tot) {
    fill(distleft, distleft + left_tot + 1, -1);
    fill(distright, distright + right_tot + 1, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= left_tot;++i)
        if (leftTo[i] == -1)
            que.push(i);
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distleft[u] > dist)break;
        for (int i = head[u];i;i = E[i].next) {
            if (!E[i].vis)continue;
            int v = E[i].to;
            if (distright[v] != -1)continue;
            distright[v] = distleft[u] + 1;
            if (rightTo[v] == -1)dist = distright[v];
            else {
                distleft[rightTo[v]] = distright[v] + 1;
                que.push(rightTo[v]);
            }
        }
    }return dist != inf;
}
bool matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        if (!E[i].vis)continue;
        int v = E[i].to;
        if (distright[v] != distleft[u] + 1)continue;
        if (distright[v] == dist && rightTo[v] != -1)continue;
        distright[v] = -1;
        if (rightTo[v] == -1 || matchpath(rightTo[v])) {
            leftTo[u] = v;
            rightTo[v] = u;
            return true;
        }
    }return false;
}

int HK(int left_tot, int right_tot) {
    int ans = 0;
    while (seacherpath(left_tot, right_tot)) {
        for (int i = 1;i <= left_tot;++i)
            if (leftTo[i] == -1 && matchpath(i))
                ++ans;
    }return ans;
}

int N, M, K;
int X, Y;
int main() {
    int tcase = 0;
    while (scanf("%d %d %d", &N, &M, &K) != EOF) {
        fill(head, head + max_n, 0);cnt = 1;
        for (int i = 1;i <= K;++i) {
            scanf("%d %d", &X, &Y);
            add(X, Y);
        }fill(leftTo, leftTo + N + 1, -1);
        fill(rightTo, rightTo + N + 1, -1);
        int res = HK(N, M);
        int ans = 0;
        for (int u = 1;u <= N;++u) {
            if (leftTo[u] == -1)continue;
            for (int i = head[u];i;i = E[i].next) {
                edge& e = E[i];
                if (e.to != leftTo[u])continue;
                e.vis = false;
                leftTo[u] = -1;rightTo[e.to] = -1;
                int tmp = HK(N, M);
                if (tmp == 0)++ans;
                e.vis = true;
                HK(N, M);
            }
        }printf("Board %d have %d important blanks for %d chessmen.\n", ++tcase, ans, res);
    }
}