km板子

求带权最大匹配，稠密图时好用，时间复杂度o（n^3），只能对完备匹配使用，网络流的费用流，用处更多更广

const int maxn=105;
const int inf=0x3f3f3f3f;
int w[maxn][maxn];
int la[maxn],lb[maxn];
bool va[maxn],vb[maxn];
int match[maxn];
int n,delta;
bool dfs(int x){
   
	va[x]=1;
	for(int y=1;y<=n;y++){
   
		if(!vb[y])
			if(la[x]+lb[y]-w[x][y]==0){
   
				vb[y]=1;
				if(!match[y]||dfs(match[y])){
   
					match[y]=x;
					return true;
				}
			}
			else delta=min(delta,la[x]+lb[y]-w[x][y]);
	}
	return false;
} 
int km(){
   
	for(int i=1;i<=n;i++){
   
		la[i]=-inf;
		lb[i]=0;
		for(int j=1;j<=n;j++)
			la[i]=max(la[i],w[i][j]);
	}
	for(int i=1;i<=n;i++)
		while(true){
   
			memset(va,0,sizeof(va));
			memset(vb,0,sizeof(vb));
			delta=inf;
			if(dfs(i))	break;
			for(int j=1;j<=n;j++){
   
				if(va[j])	la[j]-=delta;
				if(vb[j])	lb[j]+=delta;
			}
		}
	int ans=0;
	for(int i=1;i<=n;i++)	ans+=w[match[i]][i];
	return ans;
}