题目描述
设有M个工人x1, x2, …, xm，和N项工作y1, y2, …, yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。
输入格式
第一行两个整数m，n分别为工人数和工作数。
接下来一个整数s，为二分图的边数。
接下来s行，每行两个数ai,bi表示第ai个工人能胜任第bi份工作
输出格式
一个整数，表示最多能让多少个工人派到自己的胜任的工作上。
样例
【样例输入】
3 3
4
1 2
2 1
3 3
1 3
【样例输出】
3
数据范围与提示
1<=m,n<=100
1<=s<=10000
一些想法
这道题其实就是可以看作将工人排在一边，工作排在一边，用线连接工人相对应的工作，找到线最多的合法情况，也就是最大匹配问题（具体看有关二分匹配那一篇）。
变量：定义两个暂时变量用于输入工人和他可以胜任的工作，记录当前边数最大值（最大匹配值），一个标记数组（用于标记当前工作是否访问过），时间戳，一个数组储存每个工作匹配到的工人，还有一个领接表：a[x] 存储工人 x 能胜任的所有工作。
输入前面三个数，然后循环输入工人可以胜任的工作，然后添加边，储存当前工人可以胜任的工作。
然后循环每一个工人，每处理一个新工人时间戳加一，然后尝试寻找当前工人是否有增广路径（运用函数），如果有，更新最大匹配（加一），否则不变。最后输出最大匹配即可。
自定义函数：用匈牙利算法查询当前工人（当前点）是否有增广路径。
先将当前工人可以胜任的工作数量赋值（循环边界用），循环这个工人可以胜任的每一项工作，用一个值赋值当前工人胜任当前工作的值，如果标记这个数等于当前时间戳，说明这个工作已经查询访问过了，跳过这项工作（访问下一项工作），否则没有访问过，就标记为访问过，继续查询。（每次调用函数前加时间戳，确保标记当前工作数组无需重置即可区分不同轮次。）
用一个数将当前工作原匹配的工人暂时储存，然后让当前工人尝试匹配这项工作，如果这项工作原来没有工人（未匹配，工人为 0）或者原来的那个工人可以匹配到新的工作，说明当前工人可以担任这个工作，整体是可以成功的，那就找到了增广路径，返回 1（使统计最大匹配加一），如果原来的工人找不到新的 可以匹配的工作，说明当前工人担任这项工作不可行，回溯，让原来的工人继续担任这项工作，访问下一项工作，继续找当前工人的增广路径。
如果无法为当前工人找到增扩路径，返回 0。（无法增加最大匹配）
补充匈牙利算法找增广路径轮廓：将匹配 M 初始化为 0（即空集）→ 不断找增广路 → 更新匹配 → 直到找不到增广路 → 此时的 M 就是最大匹配。
AC代码
#include<bits/stdc++.h>
using namespace std;
int m,n,k,ans,x,y,v[1005],link[1005],t;
vector<int> a[1005];
bool h(int x){
int l=a[x].size();
for(int i=0;i<l;i++){
int y=a[x][i];
if(v[y]==t) continue;
v[y]=t;
int q=link[y];
link[y]=x;
if(!q||h(q)) return 1;
link[y]=q;
}
return 0;
}
int main(){
cin>>m>>n>>k;
for(int i=1;i<=k;i++){
cin>>x>>y;
a[x].push_back(y);
}
for(int i=1;i<=m;i++){
t++;
ans+=h(i);
}
cout<<ans;
return 0;
}
