圖論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);
}
鄰接矩陣 AC
2.最小點覆蓋數
選取最少的點，使任意一條邊至少有一個端點被選擇
有定理在，判斷出一個題可以用最小點覆蓋數求的時候，就直接用求最大匹配數的代碼搞
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);
}
鄰接矩陣 AC
3.最大獨立數
選取最多的點，使任意所選兩點均不相連
poj 1466 Girls and Boys
二分圖的最大獨立集
因為沒有給出具體的男生和女生，所以可以將數據擴大一倍，即n個男生，n個女生，
根據定理，最大獨立集=總數-匹配數（本題應該除以2）
![]()
給出一系列男女配對意願信息。求一個集合中的最大人數，滿足這個集合中兩兩的人不能配對。
Sample Input
7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
Sample Output
5
2
題目描述
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 510
using namespace std;
int link[maxn],vis[maxn],map[maxn][maxn],n;
int dfs(int x){
for(int i=1;i<=n;i++){
if(vis[i]==0&&map[x][i]){
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;
return 1;
}
}
}return 0;
}
int main(){
freopen("1.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
memset(map,0,sizeof(map));
memset(link,0,sizeof(link));
for(int i=1;i<=n;i++){
int u,w,v;
scanf("%d: (%d)",&u,&w);u++;
for(int j=1;j<=w;j++){
scanf("%d",&v);v++;
map[u][v]=map[v][u]=1;
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",n-ans/2);
}
}
AC
4.最小路徑覆蓋數
對於一個 DAG（有向無環圖），選取最少條路徑，使得每個頂點屬於且僅屬於一條路徑。路徑長可以為 0（即單個點）。
