二分图
显然，网上的大部分入门二分图的文章都是为了看不懂而写的。
本篇文章将把专业名词等“前置知识”移到后面，所以不用担心文章专业性。
（免责：本文章所有象形比喻等仅作方便理解用,并无恶意，若有侵权的问题请联系作者删除。）
OK，现在，我们考虑这样一个问题：
题目大意
班里有$n$个男生，$m$个女生，每个男生都有一些心仪的女生，请问最多能凑出多少对情侣？
防止杠精：这里的每一对情侣都是互相钟情的，不存在脚踏$k$条船的情况
输入格式
第一行三个整数 $n$,$m$,$k$
接下来 $k$ 行，每行两个整数 $x$，$y$，表示 $x$ 号男生对 $y$ 号女生有意思。
输出格式
一行一个整数，表示最多能凑出多少对情侣。
输入输出样例
输入 #1
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1输出 #1
2说明/提示
数据规模与约定
对于全部的测试点，保证：
$1 \leq n, m \leq 500$。
$1 \leq k \leq 5 \times 10^4$。
$1 \leq u \leq n$，$1 \leq v \leq m$。
反正我看题第一眼：
cout<<"0"<<endl;
认真的，这题咋做呢？
我们考虑男生轮流选妃。
轮到一个男生时，男生问一个自己心仪的女生有没有男友，
要是没有，那感天谢地，就选她了（目前来说）。
有的话，也没关系，让她男朋友换一个。
她男朋友想，那我试试。
他就问自己心仪的其他女生有没有男友，没有刚好，有的话——
对不起，再麻烦一下某一位女生的男友换一个。
但是男生们心仪的女生总是有限的，要是问到一个一生钟情一人的男生，那他说啥也不换啊。
对不起，你麻烦别的男生吧。
显然，有一种可能，他所有心仪的其他女生的男友都不愿意换。
那——
老子不换了！换个啥换，你有我就没有了。
于是，他也不愿意换。
麻烦他的男生就得重新找个心仪女生的男友试着谈判一下……
这个过程中一旦找到一个无主之花，那么就调剂成功了，这个男生就找到了一个心仪的女友。
但如果没有，那……
可怜的，就单身一辈子吧。
默哀。
你说要是轮到一个男生，这个男生只钟情一人，但这个人的男友已经不可调剂了，要不要可怜一下痴情人，把那女子换给他呢？
不管你怎么想，这样对答案没有贡献，不会增加情侣的对数。
我懒，所以不换。
于是，就个到了一个很好的分配情侣的方法：
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,k;
const int MAXM=5e4+5;
const int MAXN=505;
vector <int> girlfriend[MAXN];//存每个男生心仪哪些女生
int boyfriend[MAXN];//记录每个女生现在的男友，没有就是0。
bool vis[MAXN];
bool dfs(int r){
if(vis[r])return false;//这是之前直接或间接要求自己换女友的，难道他还能找他换不成。
vis[r]=1;
for(auto i:girlfriend[r]){//每个心仪的女友都问一遍
if(boyfriend[i]){//她要是有了，那就麻烦她男友再找一个
if(dfs(boyfriend[i])){//他男友同意吗？
boyfriend[i]=r;//同意，那就好，那女子的男友是我了
return true;//我找到了，我好你好大家好。
}
}
else {//她没有男友那好啊
boyfriend[i]=r;//她是我的完事了
return true;//找到了
}
}
return false;//问了一圈，没人换啊，那不换了。要是本来就单身，好吧，单就单……
}
signed main(){
cin>>n>>m>>k;
int x,y;
for(int i=1;i<=k;i++){
cin>>x>>y;
girlfriend[x].push_back(y);
}
int cnt=0;//记录情侣对数
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));//防止两个男生互相问来问去死循环，加个vis数组避开这种情况。
if(dfs(i))cnt++;//要是这个男的找到了，那就加一对情侣
}
cout<<cnt;
return 0;
}讲完了，匈牙利算法简单不？
我想大家都懂了，那上原题吧。
【模板】二分图最大匹配
题目描述
给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。
左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。
输入格式
输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。
接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。
输出格式
输出一行一个整数，代表二分图最大匹配的边数。
样例 #1
样例输入 #1
1 1 1
1 1样例输出 #1
1样例 #2
样例输入 #2
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1样例输出 #2
2提示
数据规模与约定
对于全部的测试点，保证：
- $1 \leq n, m \leq 500$。
- $1 \leq e \leq 5 \times 10^4$。
- $1 \leq u \leq n$，$1 \leq v \leq m$。
不保证给出的图没有重边。
什么是二分图？
如果我们能找到一种方法将一个图的所有顶点分成两个集合，使得不存在某一条边连接的两个点在同一个集合中，那么这个图就叫二分图。
二分图的判定方法： 如果一个图没有奇环，那么这个图就是一个二分图。
二分图的匹配： 如果我们在一个二分图里选一些边，使得任意两条边都没有共顶点的情况，那么这些边就是这个二分图的一个匹配
二分图的最大匹配： 一个二分图中所有匹配中边数最多的匹配就是这个二分图的最大匹配，可能不止一种。
增广路径： 不解释。
搬个文章：CSDN文章
增广路径是指，由一个未匹配的顶点开始，经过若干个匹配顶点，最后到达对面集合的一个未匹配顶点的路径，即这条路径将两个不同集合的两个未匹配顶点通过一系列匹配顶点相连。
至少，我认为这个定义很抽象。
然而，
匈牙利算法: 通过一条增广路径，通过取反操作，我们就能匹配更多的点。
也就是说，我们只要找到对于当前匹配找到一条增广路径，我们就能多匹配两个点，多一条边。对于固定的一个合法点集，不管是怎么匹配的，它的代价都是一样的，不会影响到其他点的情况，所以贪心找增广路的正确性可证。
多读几遍你其实就发现，
增广路径的本质不就是一个加点的调配方法吗？
而且，代码写起来并不是顺着边遍历，而是在左集合中根据右集合的匹配跳点递归，取反操作也不能真正用取反操作进行，所以，我觉得这个 增广路径 定义的超级鸡肋，当然，我觉得弃之不可惜。
但要是说增广路在网络流等其他算法中有诸多应用，或者在带权二分图中不可缺失……
当我没说。
正常变量名代码：
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,k;
const int MAXM=5e4+5;
const int MAXN=505;
vector <int> v[MAXN];
int match[MAXN];
bool vis[MAXN];
bool dfs(int r){
if(vis[r])return false;
vis[r]=1;
for(auto i:v[r]){
if(match[i]){
if(dfs(match[i])){
match[i]=r;
return true;
}
}
else {
match[i]=r;
return true;
}
}
return false;
}
signed main(){
cin>>n>>m>>k;
int x,y;
for(int i=1;i<=k;i++){
cin>>x>>y;
v[x].push_back(y);
}
int cnt=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))cnt++;
}
cout<<cnt;
return 0;
}
大佬！