二分图最大匹配KM算法之BFS版本模板

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
const int INF = 0x3f3f3f3f
ll n, a[maxn],b[maxn],c[maxn],p[maxn];
ll w[maxn][maxn];
ll lx[maxn] , ly[maxn];
ll slack[maxn];
bool visy[maxn];
ll pre[maxn];
void bfs( ll k ){
ll x , y = 0 , yy = 0 , delta;
memset( pre , 0 , sizeof(pre) );
for(int i = 1 ; i <= n ; i++ ) slack[i] = INF;
while(1){
x = linker[y]; delta = INF; visy[y] = true;
for(int i = 1 ; i <= n ;i++ ){
if( !visy[i] ){
if( slack[i] > lx[x] + ly[i] - w[x][i] ){
slack[i] = lx[x] + ly[i] - w[x][i];
pre[i] = y;
}
if( slack[i] < delta ) delta = slack[i] , yy = i ;
}
}
for(int i = 0 ; i <= n ; i++ ){
if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
else slack[i] -= delta;
}
y = yy ;
if( linker[y] == -1 ) break;
}
while( y ) linker[y] = linker[pre[y]] , y = pre[y];
}

ll KM(){
memset( lx , 0 ,sizeof(lx) );
memset( ly , 0 ,sizeof(ly) );
for(int  i = 1 ; i <= n ; i++ ){
memset( visy , false , sizeof(visy) );
bfs(i);
}
ll res = 0 ;
for(int i = 1 ; i <= n ; i++ ){
if( linker[i] != -1 ){
res += w[linker[i]][i] ;
}
}
return res;
}```