题目
有两台机器 (A,B) 分别有 (n,m) 种模式。
现在有 (k) 个任务。对于每个任务 (i) ，给定两个整数 (a_i) 和 (b_i)，
表示如果该任务在 (A) 上执行，需要设置模式为 (a_i)；
如果该任务在 (B) 上执行，需要设置模式为 (b_i)。
每台机器第一次开机默认处在0模式，且第一次开机不需要消耗时间。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
(1≤n,m≤100，1 leq k leq 1000,0 leq a_i<n,0leq b_i<m)
分析
首先先把模式为0的任务去掉，然后考虑两种模式必选其一，
以下摘自《算法竞赛进阶指南》
- 0要素：节点能分成独立的两个集合，每个集合内部有0条边
- 1要素：每个节点只能与1条匹配边相连
- 2要素：每条边有两个端点，二者至少选择一个（最小点覆盖）
所以观察到这个模型为二分图最小点覆盖，直接求最大匹配即可
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=201;
struct node{int y,next;}e[N*5];
int v[N],link[N],n,m,et,ans,upd,as[N];
inline signed iut(){
rr int ans=0,f=1; rr char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans*f;
}
inline void add(int x,int y){
e[++et]=(node){y,as[x]},as[x]=et;
}
inline bool match(int x){
for (rr int i=as[x];i;i=e[i].next)
if (v[e[i].y]!=upd){
v[e[i].y]=upd;
rr int q=link[e[i].y];
link[e[i].y]=x;
if (!q||match(q)) return 1;
link[e[i].y]=q;
}
return 0;
}
signed main(){
while (n=iut()){
m=iut(),et=ans=0;
for (rr int Q=iut(),x,y;Q;--Q){
iut(),x=iut(),y=iut();
if (!x||!y) continue;
add(x,y+n);
}
for (rr int i=1;i<=n;++i) ++upd,ans+=match(i);
printf("%d
",ans);
for (rr int i=1;i<=n+m;++i) as[i]=link[i]=0;
}
return 0;
}