【模板】二分图最大匹配

模板题:【模板】二分图匹配

概念: 什么是二分图? 二分图:二分图又称作二部图,是图论中的一种特殊模型。设 G=(V,E) 是一个无向图,如果顶点V可分割为两个互不相交的子集 (A,B) ,并且图中的每条边( i ,j )所关联的两个顶点i和j分别属于这两个不同的顶点集 ( i ∈ A , j ∈ B ),则称图G为一个二分图。

二分图

什么是二分图匹配? 二分图匹配:给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。如下图的每一个红线都是二分图的一个匹配:

二分图匹配

例题:

CoVH之柯南开锁

关键词:图结构  二分图 相关题目:[CoVH之柯南开锁][49]

题目背景

随着时代的演进,困难的刑案也不断增加... 但真相只有一个 虽然变小了,头脑还是一样好,这就是名侦探柯南!

题目描述

面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实. 他经过深思熟虑, 决定从OIBH组织大门进入...........

    OIBH组织的大门有一个很神奇的锁.

锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去. 柯南开锁 如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数.

请您帮助柯南计算出开给定的锁所需的最少次数.

输入输出格式

输入格式: 第一行 两个不超过100的正整数N, M表示矩阵的长和宽 以下N行 每行M个数 非0即1 1为凸起方格

输出格式: 一个整数 所需最少次数

输入样例:

4 4
0000
0101
0000
0100

输出样例:

2

分析及解决

若(x,y)=1,则给x→y连条边,那么该边的两个端点至少要选出一个 问题转化为:选出最少的点使以这些点为端点所有边的集和原图所有边的集合 \Leftrightarrow 最小点覆盖数 根据 König定理 我们可以知道:二分图的最大匹配等于这个图的最小点覆盖数

那么这道题就是裸的二分图最大匹配模板题了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N=102;
int n,m,e,ans=0;
bool G[N][N],vis[N];
int M[N];
inline bool dfs(int u){
rep(v,1,m){
if(G[u][v] && !vis[v]){
vis[v]=1;
if(!M[v] || dfs(M[v])){
M[v]=u;
return 1;
}
}
}
return 0;
}//匈牙利算法
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n)
rep(j,1,m)
scanf("%1d",&G[i][j]);
rep(i,1,n){
memset(vis,0,sizeof(vis));
if(dfs(i)) ++ans;
}
printf("%d\n",ans);
}