二分图匹配：
含义：把无向图G=(V,E)，分为两个集合V1,V2，所有的边都在V1,V2之间，而V1或V2内部没有边，V1中的一个点与V2中的一个点关联，称为一个匹配。
一个图是不是二分图，一般通过染色判断，用两种颜色对所有顶点染色，如果相邻顶点的颜色都不同那么就是二分图。
ps。一个图是二分图当且仅当它不含边的数量为奇数的点
常见问题：
（1）无权图：求包含边数最多的匹配，求二分图的最大匹配
（2）带权图：求边权和最大的匹配，KM算法
QUS1:求二分图的最大匹配
定义：（1）最大匹配：包含边数最多的匹配
（2）完美匹配：所有点都在匹配的边上
做法1：转化为最大流求解
把每个边转化为有向边，流量为1，在V1上加一个人为的源点s（连接所以的V1），在V2上加上一个人为的汇点t（连接所有的V2)，然后求s-->t的最大流即可
POJ 2339 Selecting Courses
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
//最大流解决二分图的最大匹配
//虚拟一个源点，到每一条的每个上课时间，7天，12节课，共84个节点，对每个课时选择上哪些课，建立权值为1的边，最后都汇集到虚拟的汇点
//EK求最大流
int mp[410][410];
int pre[410];
int N,M,K;
void input(){
memset(mp,0,sizeof(mp));
int n,m,t;
for(int i=1;i<=N;i++){
scanf("%d",&t);
mp[0][i]=1; //到这门课（源点）
for(int j=0;j<t;j++){
scanf("%d %d",&n,&m); //星期几、第几节课
mp[i][N+(n-1)*12+m]=1; //这门课---时间点
mp[N+(n-1)*12+m][84+N+1]=1; //时间点---汇点
}
}
}
queue<int> que;
bool bfs(int s,int t){
while(!que.empty()) que.pop();
que.push(s);
memset(pre,-1,sizeof(pre));
pre[s]=0;
int index;
while(!que.empty()){
index=que.front();
que.pop();
for(int i=1;i<=t;i++){
if(mp[index][i]>0&&pre[i]==-1){
pre[i]=index;
if(i==t) return 1;
que.push(i);
}
}
}
return 0;
}
int ek(int s,int t){
int summ=0;
while(bfs(s,t)){
for(int i=t;i!=s;i=pre[i]){
mp[pre[i]][i]--; //正向减
mp[i][pre[i]]++; //反向加
}
summ++;
}
return summ; //最大匹配数
}
int main(){
while(scanf("%d",&N)!=EOF){
input();
printf("%d\n",ek(0,84+N+1));
}
return 0;
}
做法2：匈牙利求解（更简单）
可以看作是最大流的特殊实现，因为二分图是一个很简单的图，所以对s,t的操作是多余的，可以直接从V1开始找增广路径
如果用邻接矩阵：时间O(V^3),空间O（V^2)
如果有邻接表：时间O(VE)，空间O(V+E)
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
//匈牙利算法求最大二分图匹配
int g[510][510];
int match[510]; //匹配结果
int reverb[510];
int k,m,m_girl,n_boy;
bool dfs(int x){ //找一个增广路径，给女孩x找一个配对男孩
for(int i=1;i<=n_boy;i++){
if(!reverb[i]&&g[x][i]){
reverb[i]=1; //预定男孩，给女孩x
//上面是
if(!match[i]||dfs(match[i])){ //情况1：男孩x还没有匹配，就直接分
//情况2：如果男孩i已经配对，尝试dfs更换原有配对，更换成功后，就有属于女孩x
match[i]=x;
return true;
}
}
}
return false; //没有喜欢的男孩 或者 更换不成功
}
int main(){
while(scanf("%d",&k)!=EOF&&k){
scanf("%d %d",&m_girl,&n_boy);
memset(g,0,sizeof(g));
memset(match,0,sizeof(match));
for(int i=0;i<k;i++){
int a,b;
scanf("%d %d",&a,&b);
g[a][b]=1;
}
int summ=0;
for(int i=1;i<=m_girl;i++){
memset(reverb,0,sizeof(reverb));
if(dfs(i)) summ++;
}
printf("%d\n",summ);
}
return 0;
}
相关的几个问题：
（1）最小路径覆盖：一个不含圈的有向图G中，G的一个路径覆盖是一个其节点不相交的路径集合P，图中的每一个节点仅包含于P中的某一条路径。求一个不含圈的有向图G的最小路径覆盖书
最小路径覆盖数=G的定点数-最小路径覆盖中的边数
how？拆点：把每个顶点拆为Xi，Yi然后连边，所求出的二分图的最大匹配数则为原图G的最小路径覆盖中的边数
so-----> 最小路径覆盖数=G的定点数-二分图的最大匹配数
（2）最小点集覆盖：最少的点让每条边都至少和其中一个点关联：
so----->最小点集覆盖=最大匹配
（3）最大独立集：
在N个点的图G中选出m个点，使这m个点两两之间没有边，求m最大值
二分图的最大独立集=节点数n-最大匹配数
二分图最优匹配：
又称带权最大匹配，每条边有权值，求最大权值和，若X,Y顶点集合个数相同，那么最优匹配也是一个完备匹配，如果个数不相等，可以通过加补点加0边实现转化。
KM算法（对匈牙利算法的贪心拓展）：
给每个顶点可行顶标，对所有的边(i,j)都有lx[i]+ly[j]>=w[i,j]成立，且对所有在完备匹配M中的边(i,j),都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最佳匹配
如果X于Y中节点个数相同并且所有点的度数都相等则一定存在完备匹配，否则补点加0边
how？
欲求完全二分图的最佳匹配，只要有匈牙利算法求其相等子图的完备匹配即可，逐次修改可行顶标的方法使对于的相等子图之最大匹配逐次增广，最后出现完备匹配。
伪代码：
int lx[maxn],ly[maxn],sx[maxn],sy[maxn],match[maxn];
int n,m;
bool path(int u){ //匈牙利
sx[u]=1;
for(int v=0;v<n;v++){
if(!sy[v]&&lx[u]+ly[v]==wei[u][v]){
sy[v]=1;
if(match[v]==-1||path(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
int bestmatch(){
int i,j;
for(i=0;i<n;i++){
lx[i]=-INF;
ly[i]=0; //初始值
for(j=0;j<n;j++){
if(lx[i]<wei[i][j]){
lx[i]=wei[i][j];
}
}
}
memset(match,-1,sizeof(match));
for(int u=0;u<n;u++){
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
if(path(u)){
break; //匹配成功，跳出进行下一个顶点的匹配
}
int dx=INF;
for(i=0;i<n;i++){
if(sx[i])
for(j=0;j<n;j++){
if(!sy[j]){
dx=min(lx[i]+ly[j]-wei[i][j],dx);
}
}
for(j=0;j<n;j++){
if(sx[j]) //对于访问过的x节点
lx[j]-=dx;
if(sy[j]) //对于访问过的y节点
ly[j]+=dx;
}
}
}
}
int main(){
return 0;
}
例题：UVA10080 Gopher II
https://www.luogu.com.cn/problem/UVA10080
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=105;
const int INF=0x3fffffff;
typedef long long LL;
typedef unsigned long long ull;
/*
题意：每只地鼠要走到距离小于等于v*t的洞里，问最少有几只地鼠会被抓走
一只地鼠一个洞，显然二分图最大匹配
建图：时间复杂度Θ（n^2）每个地鼠都暴力算一遍每个洞的哈密顿距离
二分图匹配： 匈牙利算法
当把地鼠和洞穴连边建成一个二分图后，这个二分图的最大匹配就是能躲进洞穴的地鼠的最大个数，最后我们输出 n-(最大匹配) 即可
*/
int n,m,s,vi;
int mp[maxn][maxn];
int match[maxn];
double xx[maxn],yy[maxn];
bool vis[maxn];
double dis(double x1,double y1,double x2,double y2){
return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
void input(){
memset(mp,0,sizeof(mp));
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++){
scanf("%lf %lf",&xx[i],&yy[i]); //地鼠的位置
}
for(int i=1;i<=m;i++){
double x,y;
scanf("%lf %lf",&x,&y);
for(int j=1;j<=n;j++){
if(dis(x,y,xx[j],yy[j])<=vi*s){
mp[j][i]=1;
//地鼠-->洞
}
}
}
}
bool dfs(int p){ //地洞
int tmp;
for(int i=1;i<=n;i++){
if(mp[i][p]&&!vis[i]){
vis[i]=1;
tmp=match[i];
match[i]=p;
if(tmp==0||dfs(tmp)) return 1;
match[i]=tmp; //回溯
}
}
return 0;
}
void ek(){
int res=0;
for(int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));
res+=dfs(i);
//cout<<res<<endl;
}
printf("%d\n",n-res);
}
int main(){
while(scanf("%d %d %d %d",&n,&m,&s,&vi)!=EOF){
input();
ek();
}
return 0;
}
费用流解决最优匹配
两种不同的建图方式，可以得到不同的解
（1）按照求最大匹配的建边方式，求出来的是最佳匹配（一定是完备匹配），因为S-X集合的每一条边都满流
（2）如果要求最大权匹配（不一定完备匹配），那么只需要再引入一个顶点A，从X集合的每个顶点向A连接一条容量为1，权值为0的边，然后再有A向T连接一条权值为0，容量不小于|X|的边，求最大费用最大流（分流思想）
原文：https://www.cnblogs.com/shirlybaby/p/12869906.html