前置知识
个人理解
- 匹配:一个边的集合,集合中的边之间没有公共点。
同时一个图中可以有多种匹配集合,其中最大匹配指的是边最多的那个匹配集合。 - 增广路(径):从一个非匹配点延匹配集合中任意一个非最大匹配集合走交替路直到另一个非匹配点。
这里通过反例证明延最大匹配的边走一定找不到另一个非匹配点,即延最大匹配的边走一定无法找到增广路径。 - 反证法:假设实线的匹配为最大匹配,则从1到8是一条增广路径,但显然由虚线组成的边也是一个匹配且边数更多,与假设不否,⭐故可得最大匹配 <–> 得不到增广路径
最小点覆盖
- 定义:选取尽可能少的点组成集合使得每条边都至少有一个顶点在集合中
- 性质:二分图的最小点覆盖数=该二分图的最大匹配数。
证明
设二分图的最小点覆盖数为A, 最大匹配数为B。
(1)证A >= B,因为匹配集合中的边之间没有公共点,所以至少选择B个点才能覆盖住最大匹配的边,其余非匹配边待定。
(2)证A == B成立,则表示可以取到等号,即最小点覆盖能够取到最小值B。
构造方法
构造过程:
1. 通过匈牙利算法求最大匹配
2. 从左部每个非匹配点出发去寻找增广路径(因为该匹配为最大匹配,故一定不会在右部找到另一个非匹配点)
这里要理解清楚,待会最终结论处要用。
3. 所有在此过程中经过的点都进行标记
得到的性质:
1. 左部所有非匹配点,一定被标记。---- 左部未被标记的点一定是匹配点。注意左部被标记的点中还有匹配点
2. 右部所有非匹配点,一定未被标记。(不然按照增广路定义表示找到了增广路,与最大匹配的实际不否。)
---- 右部所有被标记的点一定是匹配点。注意右部并非所有匹配点都被标记
3. 按照找增广路径的过程,有的匹配边会选,有的不会选,故匹配边的左右点要么同时被标记,要么同时未被标记。
结论:最终要选择的点,左部未被标记的点和右边被标记的点。
证明:
(1)选出的点恰好等于最大匹配边数:
因为将右部被标记的点(匹配点)按照性质3对应到左部,则为左部被标记的匹配点(全部来源于右部),加上左部未被标记的匹配点。则为左部总的匹配点数,即匹配边数。
(2)选出的点恰好能覆盖所有的边:
将所有的边分成:1.最大匹配边 2.从左部非匹配点走到右部匹配点的非匹配边 3.其他非匹配边
则左部未被标记的点能够到达3,右边被标记的点能够到达1和2。
故可以覆盖
由上述证明可得:二分图的最小点覆盖数=该二分图的最大匹配数
关于本题
- 所有的任务完成方式均可以看做是二分图的边,即任务数为边数,左右端点即模式
- 对于有一个端点为0的边,可直接忽略,因为按照题意不必顾忌任务顺序,因此可以理解为不必开机直接做完。
剩下的任务就是要被覆盖的边,找出最小点覆盖集即可。
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110, M = 1010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool find(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
st[j] = true;
if (!match[j] || find(match[j])) {
match[j] = u;
return true;
}
}
return false;
}
int main() {
while (cin >> n1 >> n2 >> m, n1) {
memset(h, -1, sizeof h);
memset(match, 0, sizeof match);
idx = 0;
while (m--) {
int i, a, b;
scanf("%d %d %d", &i, &a, &b);
if (!a || !b) continue;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; ++i) {
memset(st, 0, sizeof st);
if (find(i)) res++;
}
printf("%d\n", res);
}
return 0;
}