题目链接
376. 机器任务
有两台机器 \(A，B\) 以及 \(K\) 个任务。
机器 \(A\) 有 \(N\) 种不同的模式（模式 \(0 \sim N-1\)），机器 \(B\) 有 \(M\) 种不同的模式（模式 \(0 \sim M-1\)）。
两台机器最开始都处于模式 \(0\)。
每个任务既可以在 \(A\) 上执行，也可以在 \(B\) 上执行。
对于每个任务 \(i\)，给定两个整数 \(a[i]\) 和 \(b[i]\)，表示如果该任务在 \(A\) 上执行，需要设置模式为 \(a[i]\)，如果在 \(B\) 上执行，需要模式为 \(b[i]\)。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 \(N, M, K\)。
接下来 \(K\) 行，每行三个整数 \(i, a[i]\) 和 \(b[i]\)，\(i\) 为任务编号，从 \(0\) 开始。
当输入一行为 \(0\) 时，表示输入终止。
输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。
数据范围
\(N,M < 100 , K < 1000\)
\(0 \le a[i] < N\)
\(0 \le b[i] < M\)
输入样例：
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
输出样例：
3
解题思路
二分图最小点覆盖
点覆盖即选择若干点使得任意的边都至少有一个被选择的点，最小点覆盖即选择的点数最少
对于二分图，有结论：\(最大匹配=最小点覆盖\)
证明：不难证明对于最大匹配，可以在匹配边的任意一端选择一个点，即 \(最小点覆盖\geq 最大匹配\)，不妨构造证明 \(最大匹配=最小点覆盖\)，一开始分为左右两部，对于左部的所有非匹配点都开始做一遍增广（\(非匹配点,匹配点,非匹配点,\dots\)），但由于是最大匹配，即最后不可能走到非匹配点，标记所有遍历到的点，对此不难发现如下性质：
- 左边所有非匹配点都被标记
- 右边所有非匹配点都没有被标记（否则说明找到了增广路）
- 对于匹配边而言，两边要么同时被标记要么同时未被标记（由增广路径很容易得到）
开始构造：对于每个匹配边，如果左右两边都被标记的话则选择右边，否则，即两边同时未被标记，此时选择左边
\(color{red}{为什么？}\)
显然，不可能存在非匹配点和非匹配点连边，否则说明找到一条增广路径，与最大匹配矛盾，故只需要讨论 \(匹配点\) 和 \(非匹配点\) 的边以及 \(非匹配点\) 和 \(匹配点\) 的边，对于 \(非匹配点-匹配点\)，由于左部的非匹配点都被标记，按照构造方法，此时该 \(匹配点\) 也应该被标记，由性质 \(3\)，这时该匹配点是被选择的，所以这样的边能够被覆盖到；对于 \(匹配点-非匹配点\)，如果左部的 \(匹配点\) 被标记的话，此时该 \(非匹配点\) 会被标记，这与性质 \(2\) 矛盾，故此时 \(匹配点\) 未被标记，即此时该 \(匹配点\) 也是被选择，这样所有的边都能被覆盖
本题先处理两种模式为 \(0\) 的情况，因为这种模式一开始就可以处理掉，然后用任务表示边，两个端点即两种模式，即任意一种模式都可以消除这条边，正好对应二分图的最小点覆盖
- 时间复杂度：\(O(nm)\)
代码
// Problem: 机器任务
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/378/
// Memory Limit: 10 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=105;
int n,m,k;
bool g[N][N],st[N];
int match[N],color[N];
bool find(int x)
{
for(int i=0;i<m;i++)
if(g[x][i]&&!st[i])
{
st[i]=true;
if(match[i]==0||find(match[i]))
{
match[i]=x;
return true;
}
}
return false;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(g,0,sizeof g);
memset(match,0,sizeof match);
scanf("%d%d",&m,&k);
while(k--)
{
int i,a,b;
scanf("%d%d%d",&i,&a,&b);
if(a==0||b==0)continue;
g[a][b]=true;
}
int res=0;
for(int i=0;i<n;i++)
{
memset(st,0,sizeof st);
if(find(i))res++;
}
printf("%d\n",res);
}
return 0;
}