bool dfs(int u){
	vx[u]=1;
	for (int v=1;v<=n;v++){
		if(!vy[v]){
			if(lx[u]+ly[v]==e[u][v]){
				vy[v]=1;
				if(!py[v] || dfs(py[v])){
					py[v]=u;
					return 1;
				}
			}
			else{
				slack[v]=min(slack[v],lx[u]+ly[v]-e[u][v]);
			}
		}
	}
	return 0;
}
void KM(){
	for (int i=1;i<=n;i++){
		while(1){
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			fill(slack+1,slack+1+n,INF);
			d=INF;
			if(dfs(i)) break;
			for (int j=1;j<=n;j++){
				if(!vy[j]) d=min(d,slack[j]);
			}
			for (int j=1;j<=n;j++){
				if(vx[j]) lx[j]-=d;
				if(vy[j]) ly[j]+=d;
			}
		}
	}
}

bool dfs(int u){
	vx[u]=1;
	for (int v=1;v<=n;v++){
		if(!vy[v]){
			if(lx[u]+ly[v]==e[u][v]){
				vy[v]=1;
				if(!py[v] || dfs(py[v])){
					py[v]=u;
					return 1;
				}
			}
			else{
				d=min(d,lx[u]+ly[v]-e[u][v]);
			}
		}
	}
	return 0;
}
void KM(){
	for (int i=1;i<=n;i++){
		while(1){
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			d=INF;
			if(dfs(i)) break;
			for (int j=1;j<=n;j++){
				if(vx[j]) lx[j]-=d;
				if(vy[j]) ly[j]+=d;
			}
		}
	}
}

在写的过程中遇到了这样的两种写法，一个记录全局松弛最小量，另一个对每一个求完再扫一遍。

不是很懂为什么在运行时间上大相径庭，前一个会T的点第二个才几十毫秒，做的一些其他的题也是这样。