最小樹形図——朱劉アルゴリズム

ブログアドレス:−>C l i c k H e r<−>Click Here<−−>ClickHere<−>ClickHere<−
最近、最小生成木の問題を探していますが、難易度は限られています.点進の青問題紫問題は「生成木」と何の関係もありません.そこで、なぜか最小の木の形図の問題を見つけました.それから、もちろん辛くありません.
无駄に勉强して、まだ何もできませんが、结局私达は时間があって、しばらく磨いてやっと少し分かりました......
本題に入りました・・・
定義＃テイギ＃
正直今まで定義がよく分からなかったのですが...
大体1枚の有向図を与えて、ルートノードr o o t root rootを指定して、1本の有向木を求めて、選択した辺の重み値と最小にします
まずすべての点を选ぶに违いない......さもないとこのテーマには何の意味があるのか......
そして有向樹……根ノードの入度は0 0 0に違いないと説明していますが、他の店の入度は最大1 1 1、出度はどうでもいいのが明らかです
そしてどうやって求めたのか・・・
朱-劉アルゴリズム
とりあえずこの名前は突っ込まないで・・・ちょっと変だけど
朱劉アルゴリズムの核心は何ですか.また欲張りだよ・・・
(なぜ「また」と言うのでしょうか?前に書いたEK EKも欲張りなので・・・)
まず定義に基づいて,各非ルートノードの入度が最も多く,必ず1 1 1であることが分かったので,各エッジの終点に対して最小の重み値を持つエッジを貪欲に選択した.
この場合、選択したエッジの一部は必ずしも木ではありませんが、ループが現れる可能性があるので、これらのループを縮めて(ここではT a r j a n Tarjan Tarjanを使わず、選択したエッジに基づいて終点から起点へ)、この手順を繰り返します.
ただし、ループを探す前に、その点につながるエッジの重みを付けます.その点につながるエッジを1つ変えるには、この別のエッジの重みではなく、別のエッジの重みから元のエッジの重みを減算する必要があります.計算が不便なので、まずエッジの重みを元のエッジの重みを減算すればいいのです
そう言えば混乱するかも・・・コードで会おう・・・
朱-劉アルゴリズムは最小の木の形の図のテンプレートを求めますtext{huge朱-劉アルゴリズムは最小の木の形の図を求めますquadテンプレート}朱-劉アルゴリズムは最小の木の形の図のテンプレートを求めます

bool ZhuLiu()
{
	while(1)
	{
		tot=0;//     
		memset(bel,0,sizeof(bel));
		memset(f,0,sizeof(f));
		memset(minx,60,sizeof(minx));
		for(int i=1;i<=m;i++)
		{
			int u=e[i].u,v=e[i].v;
			if(u^v && minx[v]>e[i].dis)//                    
			{
				minx[v]=e[i].dis;
				faz[v]=u;//          
			}
		}
		minx[rt]=0;
		for(int i=1;i<=n;i++)//     ，  
		{
			int u;
			if(minx[i]==inf) return 0;//            
			ans+=minx[i];//    
			for(u=i;u!=rt && f[u]!=i && !bel[u];u=faz[u]) f[u]=i;
        //   f              “    ”，     ，                   
			if(u!=rt && !bel[u])//             
			{
				bel[u]=++tot;
				for(int v=faz[u];v!=u;v=faz[v]) bel[v]=tot;
			}
		}
		if(!tot) return 1;//           ，    
		for(int i=1;i<=n;i++) if(!bel[i]) bel[i]=++tot;//           
		for(int i=1;i<=m;i++)
		{
			int w=minx[e[i].v];
			e[i].u=bel[e[i].u];
			e[i].v=bel[e[i].v];
			int u=e[i].u,v=e[i].v;
			if(u!=v) e[i].dis-=w;//                     ，                
		}
		n=tot;
		rt=bel[rt];
	}
}

スラグなので、B u g Bug Bugを探してください.
F i n . Fin. Fin.