概念
二分图
若一张图中所有顶点能涂成两种颜色，且相邻两点颜色不同，则该图为二分图。
匹配
若二分图 (G) 的子图 (M) 满足 (M) 的任意两条边都不连接同一个顶点，则称 (M) 是 (G) 的一个匹配。
最大匹配
(|M|)最大的 (M) 是 (G) 的最大匹配。
求最大匹配
匈牙利算法
设 (n_1) 为二分图左侧顶点数， (n_2) 为二分图左侧顶点数， (m) 为二分图边数，则复杂度 (O(n_1n_2)) 。
Code
#include<cstdio>
#define maxn 1002
#define maxm 1000002
using namespace std;
struct edge{
int to,next;
};
edge e[maxm];
int head[maxn],cnte;
void add(int u,int v){
e[++cnte].to=v;
e[cnte].next=head[u];
head[u]=cnte;
}
int c[maxn],n1,n2,m;
bool vis[maxn];
bool dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!c[v]||dfs(c[v])){
c[v]=u;
return 1;
}
}
return 0;
}
int match(){
int ret=0;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++)vis[j]=0;
if(dfs(i))ret++;
}
return ret;
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); //注意是建单向边
}
printf("%d
",match());
return 0;
}
例题
洛谷 P3386 【模板】二分图匹配
二分图匹配模板题。
POJ - 3041 Asteroids
题意
给你一个 (n) 行 (m) 列的矩阵，矩阵中用若干个点，每次你可以消去一整行或一整列的点，求最少多少次能把所有点消完。
分析
我们设 (u_i(iin [1,n])) （行号集合）为二分图左侧顶点， (v_i(iin [1,m])) （列号集合）为二分图右侧顶点，对于矩阵中的每一个点 ((x,y)) ，连边 ((x,y)) ，这样，题目就转化成了求大小最小的顶点集合(V)，使得所有边都依附于 (V) 中的顶点。这其实就是最小点覆盖问题，转化为二分图最大匹配求解。
Code
#include<cstdio>
#define maxn 1002
#define maxm 1000002
using namespace std;
struct edge{
int to,next;
};
edge e[maxm];
int head[maxn],cnte;
void add(int u,int v){
e[++cnte].to=v;
e[cnte].next=head[u];
head[u]=cnte;
}
int c[maxn],n1,n2,m;
bool vis[maxn];
bool dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!c[v]||dfs(c[v])){
c[v]=u;
return 1;
}
}
return 0;
}
int match(){
int ret=0;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++)vis[j]=0;
if(dfs(i))ret++;
}
return ret;
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u>n1||v>n2)continue;
add(u,v);
}
printf("%d
",match());
return 0;
}
列队
问题描述
Sylvia是一个热爱学习的女孩子。
在平时的练习中，他总是能考到std以上的成绩，前段时间，他参加了一场练习赛，众所周知，机房是一个 (n* n) 的方阵。这天，他又打爆了std，感到十分无聊，便想要hack机房内同学的程序，他会挑选一整行或一整列的同学进行hack ( 而且每行每列只会hack一次 )，然而有些同学不是那么好惹，如果你hack了他两次，他会私下寻求解决,Sylvia十分害怕，只会hack他们一次。假设Sylvia的水平十分高超，每次hack都能成功，求他最多能hack多少次？
输入格式
第一行两个数 (n,x) 表示机房的大小和不好惹的同学个数
接下来 (x) 行，每行两个数 (x,y) 表示不好惹的同学坐标
输出格式
一个数表示最多hack多少次
样例输入
2 1
1 1
样例输出
6
样例说明
他可以hack第一行、第二行、第二列一共6次
数据规模
(nle 1000,xle 4000)
分析
对每个点 ((x,y)) ，连边 ((x,y)) ，表示点 ((x,y)) 不能被hack两次，求出最大匹配，用 (n* 2) 减去最大匹配即可。
Code
#include<cstdio>
#define maxn 1002
#define maxm 1000002
using namespace std;
struct edge{
int to,next;
};
edge e[maxm];
int head[maxn],cnte;
void add(int u,int v){
e[++cnte].to=v;
e[cnte].next=head[u];
head[u]=cnte;
}
int n,m,c[maxn];
bool vis[maxn];
bool dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!c[v]||dfs(c[v])){
c[v]=u;
return 1;
}
}
return 0;
}
int match(){
int ret=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)vis[j]=0;
if(dfs(i))ret++;
}
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
printf("%d",n*((n<<1)-match()));
return 0;
}
XJOI 1570 双子树
题意
这一天，随身带来的干粮豆吃玩了，必须有人去找些食物来吃才行。可Z4的懒惰是出了名的，谁会愿意去呢？经过一番商讨，大家最后决定以老规矩“猜十次”的方式决定人选。可怜的立方由于猜拳技术不过关，屡战屡败，只好踏上觅食的征途。
立方后来找到了两棵奇怪的树，由于它们的形态十分相像，双子座的立方一时兴起便把它们命名为“双子树”。可双子树的果实能不能吃呢？“管它呢，先摘了再说。”于是身手敏捷的立方便爬上其中一棵，摘下一个大大的果实。可就在此时，另一棵却有几个果实坠地。
立方细心一看，发现这双子树上的某些果实有一些细丝相连，只要摘下其中一棵树的某一个果实，另一棵树将会有相应的一个或多个（也可能没有）果实坠地而摔坏，这些果实都和摘下的果实用细丝相连。摔坏的果实当然不能吃了。而且，立方发现，那些细丝是没办法弄断的，除非摘下它两端的果实的其中一个。由于这时只有立方一人（好没义气的Z4啊……），他只能眼睁睁地看着它们摔坏。也就是说，立方无法同时摘取任一条细丝两端上的两个果实。于是，不同的摘法最后会得到不同数量的果实，而立方将会用随身带的一个容量为 (V) （表示能装 (V) 个果实）的大袋子将它们装好。
馋嘴的立方当然希望摘得越多越好啦，那么，他最多可以得到多少个果实呢？
特别地，任两个果实间最多只会有一条细丝相连，同一棵树上的果实间不会有细丝相连，当袋子装满后，立方的口还可以塞进一个。
输入格式
输入文件tree.in的第一行包括四个整数 (V) （ (0<=V<=1000) ），(N_1,N_2) 和 (M) ，分别表示袋子的容量，第一棵树上的果实个数，第二棵树上的果实个数和细丝总数。为了方便计算，立方人为地把果实分别按 (1..N_1) 和 (1..N_2) 标号。
接下来有M行，每行有两个整数 (A,B)（(1le Ale N_1,1le Ble N_2)），表示第一棵树上的果实 (A) 和第二棵树上的果实 (B) 有一条细丝相连。
输出格式
输出文件tree.out仅有一个整数，表示立方最多能得到的果实个数。
样例输入&输出
样例1：
10 3 3 5
1 2
2 1
2 2
2 3
3 2
4
样例2：
2 4 4 4
1 1
2 2
3 3
4 4
3
数据范围
(0le Vle 1000,0le N_1,N_2le 500)
时间限制：
1000
空间限制：
65536
提示：
样例1中，立方最后摘取了第一棵树上的1、3和第二棵树上的1、3。
样例2中，立方本来最多可以摘4个果实，但由于袋子容量仅为2，再加上他口中的一个，最后他只能得到3个。
分析
求出最大匹配数，答案即为 (N_1+N_2-) 最大匹配数。
Code
#include<cstdio>
#include<algorithm>
#define maxn 1002
#define maxm 1000002
using namespace std;
struct edge{
int to,next;
};
edge e[maxm];
int head[maxn],cnte;
void add(int u,int v){
e[++cnte].to=v;
e[cnte].next=head[u];
head[u]=cnte;
}
int c[maxn],V,n1,n2,m;
bool vis[maxn];
bool dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!c[v]||dfs(c[v])){
c[v]=u;
return 1;
}
}
return 0;
}
int match(){
int ret=0;
for(int i=1;i<=n1;i++){
for(int j=1;j<=n2;j++)vis[j]=0;
if(dfs(i))ret++;
}
return ret;
}
int main(){
scanf("%d%d%d%d",&V,&n1,&n2,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
printf("%d
",min(V+1,n1+n2-match()));
return 0;
}
带权最大的完美匹配
KM算法
Code
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=103,INF=1050000000;
int c[maxn],lc[maxn],ld[maxn],slack[maxn],n,g[maxn][maxn];
bool visc[maxn],visd[maxn];
bool dfs(int u){
visd[u]=1;
for(int v=1;v<=n;v++){
int tmp=ld[u]+lc[v]-g[u][v];
if(!visc[v]&&!tmp){
visc[v]=1;
if(!c[v]||dfs(c[v])){
c[v]=u;
return 1;
}
}
else if(tmp<slack[v]){
slack[v]=tmp;
}
}
return 0;
}
int km(){
for(int i=1;i<=n;i++){
c[i]=lc[i]=ld[i]=0;
for(int j=1;j<=n;j++){
ld[i]=max(ld[i],g[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)slack[j]=INF;
while(1){
for(int j=1;j<=n;j++)visc[j]=visd[j]=0;
if(dfs(i))break;
int res=INF;
for(int v=1;v<=n;v++){
if(!visc[v]){
res=min(res,slack[v]);
}
}
for(int u=1;u<=n;u++){
if(visd[u]){
ld[u]-=res;
}
}
for(int v=1;v<=n;v++){
if(visc[v]){
lc[v]+=res;
}
else{
slack[v]-=res;
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++)ans+=ld[i]+lc[i];
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=-g[i][j];
}
}
printf("%d
",-km());
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=-g[i][j];
}
}
printf("%d
",km());
return 0;
}