图论3 二分图匹配
可以先在这里学学http://www.renfei.org/blog/bipartite-matching.html
模板
据上面的博客可知，二分图匹配可以分4种类型
最大匹配数：最大匹配的匹配边的数目
最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
最大独立数：选取最多的点，使任意所选两点均不相连
最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
定理2：最大匹配数 = 最大独立数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数
1.最大匹配数
最大匹配的匹配边的数目
洛谷P3386 【模板】二分图匹配
P3386 【模板】二分图匹配 难度 提高+/省选- 题目背景 二分图 题目描述 给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数 输入输出格式 输入格式： 第一行，n,m,e 第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 输出格式： 共一行，二分图最大匹配 输入输出样例 输入样例#1： 1 1 1 1 1 输出样例#1： 1 说明 n,m<=1000，1<=u<=n，1<=v<=m 因为数据有坑，可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。 算法：二分图匹配题目描述
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxm 100010
#define maxn 1010
using namespace std;
int n,m,E,num,head[maxm],link[maxn],vis[maxn],sum;
struct node{
int to,pre;
}e[maxm];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
int dfs(int x){
for(int i=head[x];i;i=e[i].pre){
int v=e[i].to;vis[v]=1;
if(link[v]==0||dfs(link[v])){
link[v]=x;return 1;
}
}return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&E);
int x,y;
for(int i=1;i<=E;i++){
scanf("%d%d",&x,&y);
Insert(x,y+n);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))sum++;
}
printf("%d",sum);
} 边表 RE+MLE#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int n,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;
int dfs(int x){
for(int i=1;i<=m;i++)
if(vis[i]==0&&re[x][i]){
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;return 1;
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&e);
int x,y;
for(int i=1;i<=e;i++){
scanf("%d%d",&x,&y);
re[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d",ans);
} 邻接矩阵 AC2.最小点覆盖数
选取最少的点，使任意一条边至少有一个端点被选择
有定理在，判断出一个题可以用最小点覆盖数求的时候，就直接用求最大匹配数的代码搞
poj3041Asteroids
跟上一个题按同一个套路来
题意：给出一个n*n的矩阵和矩阵上m个点，问你最少删除了多少行或列之后，点能全部消失。（联想：给出一张图上的m条边的n个相交顶点(xi, yi)，问最少用其中的几个点，就可以和所有的边相关联） 思路：匈牙利算法的最小覆盖问题：最小覆盖要求在一个二分图上用最少的点（x 或 y 集合的都行），让每条连接两个点集的边都至少和其中一个点关联。根据konig定理：二分图的最小顶点覆盖数等于最大匹配数。理解到这里，将(x,y)这一点，转化为x_y的一条边，把x = a的这一边，转化为(a)这一点，剩下的就是基础的匈牙利算法实现了。描述
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 501
#define maxm 10010
int n,k,num,head[maxm],link[maxn],vis[maxn];
struct node{
int to,pre;
}e[maxm];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
int dfs(int x){
for(int i=head[x];i;i=e[i].pre){
int v=e[i].to;
if(vis[v]==0){
vis[v]=1;
if(link[v]==0||dfs(link[v])){
link[v]=x;return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&k);int x,y;
for(int i=1;i<=k;i++){
scanf("%d%d",&x,&y);
Insert(x,y);
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d",ans);
} 边表 AC#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int n,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;
int dfs(int x){
for(int i=1;i<=m;i++)
if(vis[i]==0&&re[x][i]){
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&e);m=n;
int x,y;
for(int i=1;i<=e;i++){
scanf("%d%d",&x,&y);
re[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d",ans);
} 邻接矩阵 AC3.最大独立数
选取最多的点，使任意所选两点均不相连
4.最小路径覆盖数
对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。