[KMアルゴリズム/坤Mアルゴリズム]二分図帯域重みマッチング

坤Mアルゴリズムには限界がある:帯域権の最大マッチングは必ず完備マッチングであることを要求するが効率が高い:坤MアルゴリズムΘ ( n 3 )\Theta(n^3) Θ(n 3)、料金フローΘ (過ごせる)Theta(過ごせる)Θ(できる)
奇奇怪怪の定義:

トップラベル頂点マーク値、左部i i iノードトップラベルA i_を記入i Ai,右部j j jノードトップマークB j B_j Bj、A i+B j≧w iを満たす↔ j A_i+B_j\geq w_{i\leftrightarrow j} Ai​+Bj​≥wi↔j​

インタリーブツリーは左部ノードからマッチングを探すのに失敗し、DFS中にアクセスしたすべてのノードがインタリーブツリー層と層との間のエッジを構成し、マッチングエッジと非マッチングエッジとの形でインタリーブ

が現れる.

等しいサブマップΣi∈S A,j∈S B A i+B j=Σi∈S A,j∈S B w i↔ j\sum_{i\in S_A,j\in S_B}A_i+B_j=\sum_{i\in S_A,j\in S_B}w_{i\leftrightarrow j} ∑i∈SA​,j∈SB​​Ai​+Bj​=∑i∈SA​,j∈SB​​wi↔j​

結論:各等しいサブマップが完全にマッチングされると,二分図には最大マッチング証明がある:二分図Σi∈S Aに対してj∈S B A i+B j≧Σi∈S A,j∈S B w i↔ j\sum_{i\in S_A,j\in S_B}A_i+B_j\geq\sum_{i\in S_A,j\in S_B}w_{i\leftrightarrow j} ∑i∈SA​,j∈SB​​Ai​+Bj​≥∑i∈SA​,j∈SB​​wi↔j,現在エッジ重み和が最大値であるトップマークの和に達しているので,これ以上大きくすることはできない.
アルゴリズム:トップラベルを割り当て、左部をエッジ重み(A i=max⁡{w i↔ j } A_i=\max\{w_{i\leftrightarrow j}\} Ai​=max{wi↔j})、右部はゼロにしてトップマークを修正させ、等しいサブマップが見つからない場合はトップマークを修正する際に既存のマッチングの重み値は変更されず、アルゴリズムは完全なマッチングが見つかるまでトップマークを正確に修正する
上付き文字を修正することを考慮してDFSを発見した場合、左部から右部まで歩いたのはすべて非整合辺であり、右部から左部まで歩いたのはすべて整合辺であり、走整合辺を修正する必要はない.この辺を加えること,すなわち左部点i∈T iin T i∈T,右部点j∉T jotin T j∈/T(おそらく衆点の1つ)を考慮し,この辺を加えることで,等しいサブマップの辺A i+B j=w iを構築する必要がある.↔ j A_i+B_j=w_{i\leftrightarrow j} Ai​+Bj​=wi↔jそもそもA i+B j≧w i↔ j A_i+B_j\geq w_{i\leftrightarrow j} Ai​+Bj​≥wi↔j,従ってA i+B j−w iを減少させる↔ j A_i+B_j-w_{i\leftrightarrow j} Ai​+Bj​−wi↔j,最小注意が必要であり,値を変更したのはインタリーブツリーにおけるトップラベルであり,非インタリーブツリーにおけるトップラベルは変わらない.
板題はなぜかWAなのですが、スケジュール通りのコードです

#include
using namespace std;
#define in Read()
int in{
	int i=0,f=1;char ch=0;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') ch=getchar();
	while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar();
	return i*f;
}

typedef long long ll;
const int N=505;
const int INF=2147483647;
int n,m;
int w[N][N],mat[N];
int la[N],lb[N],upd[N],delta;
bool va[N],vb[N];
// upd for updating delta, which if b
otin T

bool DFS(int u){
	va[u]=true;
	for(int v=1;v<=n;++v){
		if(!vb[v])
			if(la[u]+lb[v]-w[u][v]) upd[v]=min(upd[v],la[u]+lb[v]-w[u][u]);
			else{
				vb[v]=true;
				if(!mat[v]||DFS(mat[v])){
					mat[v]=u;
					return true;
				}
			}
	}
	return false;
}

ll 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)
		// Until get the match
		// modify topmark each time
		while(true){
			memset(va,0,sizeof(va));
			memset(vb,0,sizeof(vb));
			for(int j=1;j<=n;++j) upd[j]=INF;
			if(DFS(i)) break;
			for(int j=1;j<=n;++j)
				if(!vb[j]) delta=min(delta,upd[j]);
			for(int j=1;j<=n;++j){
				if(va[j]) la[j]-=delta;
				if(vb[j]) lb[j]+=delta;
			}
		}
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=w[mat[i]][i];
	return ans;
}

int main(){
	n=in,m=in;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			w[i][j]=-INF;
	for(int i=1;i<=n;++i){
		int u=in,v=in,val=in;
		w[u][v]=max(w[u][v],val);
	}
	printf("%lld
",KM());
	for(int i=1;i<=n;++i) printf("%d ",mat[i]);
	return 0;
}

優秀なBFSはコードを思わないでこのDFSは十分に気持ち悪いことに加えて私はyyyrの巨大なコードを見ることができません
はい、坤Mはそうです.