二分图匹配

二分图匹配

九月 05, 2021

二分图的匹配

二分图的最大匹配

增广路

一条匹配边与非匹配边交替出现的路径叫做增广路

匹配边：两个点已经处于已选集合里面的边

非匹配边：这条边有个点不属于已经选过的集合里面的边

匈牙利算法

在二分图里面交替找增广路的算法，然后把增广路取反直到不存在增广路为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool dfs(int u){
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!vis[v]){
			vis[v]=1;
			if(!match[v]||dfs(match[v])){
                 //这里对应着两种情况，一种是还没有匹配，另一种是可以腾出空间
				match[v]=u;
				return true;
             }
        }
    }
    return false;
}
int main(){
    int ans=0;
    for(int i=1;i<=N;i++)
        //这个N是左边的端点
        if(dfs[i])ans++;
}
  1. 1. 二分图的匹配
    1. 1.1. 二分图的最大匹配
      1. 1.1.1. 增广路
      2. 1.1.2. 匈牙利算法