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