[POJ 3164]Command Network有向図の最小ツリー図(朱劉アルゴリズム)

Command Network
タイトルリンク:http://poj.org/problem?id=3164
テーマ:
ルートノードからすべてのノードにアクセスでき、パスが最も短い方向図があります.すなわち最小ツリー図を求める.
===================================================================SCUTのblog================================================================================================================================最小樹形図の最初のアルゴリズムは1965年に朱永津と劉振宏が提案した複雑度O(VE)のアルゴリズムである.ツリー図が存在するか否かを判断する方法は簡単で、vを元に一度図の遍歴をすればよいので、以下のアルゴリズムではツリー図が存在しない場合は考慮しない.すべての操作が開始される前に、図中のすべてのセルフループをクリアする必要があります.明らかに,自己ループはいずれのツリー図にも不可能である.この操作を進めてこそ、やっと複雑さがO(VE)であることが保証される.まず、ルートを除いた各ポイントに1つのエッジを選択します.このエッジは、すべてのエッジの中で最も小さいものでなければなりません.すべての最小エッジが選択され、このエッジセットに方向リングが存在しない場合、このセットが図の最小ツリー図であることを証明することができます.この証明は難しくない.有向リングが存在する場合は、この有向リングで呼ばれる人工頂点を図中のエッジの重みを変更します.ある点uがそのリング上にあると仮定し、このリングの中でuを指す辺権がin[u]であるとすると、uから出発する各辺(u,i,w)に対して、新しい図に(new,i,w)を接続する辺であり、newは新しく追加された人工頂点である.各uに入るエッジ(i,u,w)について、新しい図にエッジ(i,new,w−in[u])のエッジが確立される.なぜエッジに入る重みがin[u]を減算するのか,これは後で説明するが,ここではまずアルゴリズムのステップを与える.そして,新図における最小ツリー図の重みと,旧図に収縮されたそのリングの重みとが,原図における最小ツリー図の重みであることが証明される.上の結論も証明しない.次に,上記の結論に基づいて,なぜ出辺の重みが変わらないのか,入辺の重みをin[u]減算するのかを説明する.新図中の最小ツリー図Tについては、人工ノードを指す辺をeとする.人工ノードを展開した後,eはリングを指す.元のeがuを指すと仮定し,このときリング上のuを指すエッジin[u]を削除すると,元の図のツリー図が得られる.新しい図のeの重みw'(e)が元の図のeの重みw(e)からin[u]の重みを減算すると、in[u]を削除し、eを元の図状態に復元するとき、このツリーの重みは依然として新しい図のツリーの重みリングの重みであり、この重み値は最小ツリーの重み値であることがわかります.したがって,ノードを展開した後も最小ツリー図が得られた.すべての人工ノードを徐々に展開すると,初期図の最小ツリー図が得られる.スマートに実現すれば,最小エッジO(E),リングO(V),収縮O(E)を見つけることができ,その中でリングO(V)を探すにはここで少しのテクニックが必要である.このように収縮するたびの複雑さはO(E)で、それから最大何回収縮しますか?私たちは最初にすべての自環を取ったので、私のドアは各環が少なくとも2つの点を含んでいることを知っていて、1つの点に収縮した後、総点数が少なくとも1減少しました.図全体が1点に縮小すると,最小ツリー図は求めなくてもよい.だから私たちはV-1回の収縮しかできないことが多いので、複雑さは自然にO(VE)です.このことから,最初にループを除去しなければ,理論的複雑さはループの数に関係することが分かる.分割線の上からサスケ_SCUTのblog============================================下面は朱劉アルゴリズムの構造図である

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 110
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef double type;
using namespace std;
int n, m;
struct point
{
    double x, y;
}p[maxn];
struct node
{
    int u, v;
    type w;
}e[maxn * maxn];
double dis(point a, point b)
{
    return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init()
{
    for(int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &e[i].u, &e[i].v);
        e[i].u--, e[i].v--;
        if (e[i].u != e[i].v) e[i].w = dis(p[e[i].u], p[e[i].v]);
        else e[i].w = INF; //     
    }
}
int pre[maxn], id[maxn], vis[maxn];
type in[maxn];
type Directed_MST(int root, int NV, int NE)
{
	type ret = 0;
	while(true)
    {
		//1.     
		for (int i = 0; i < NV; i++) in[i] = INF;
		for (int i = 0; i < NE; i++)
		{
			int u = e[i].u;
			int v = e[i].v;
			if(e[i].w < in[v] && u != v)
			{
				pre[v] = u;
				in[v] = e[i].w;
			}
		}
		for (int i = 0; i < NV; i++)
		{
			if(i == root) continue;
			if(in[i] == INF) return -1; //           ,       
		}
		//2.  
		int cntnode = 0;
		mem(id,-1);
        mem(vis, -1);
		in[root] = 0;
		for (int i = 0; i < NV; i++)
        {//     
			ret += in[i];
			int v = i;
			while(vis[v] != i && id[v] == -1 && v != root)
            {
				vis[v] = i;
				v = pre[v];
			}
			if(v != root && id[v] == -1)
            {
				for(int u = pre[v] ; u != v ; u = pre[u])
					id[u] = cntnode;
				id[v] = cntnode ++;
			}
		}
		if(cntnode == 0) break;//  
		for (int i = 0; i < NV; i++) if(id[i] == -1)
			id[i] = cntnode ++;
		//3.  ,    
		for (int i = 0; i < NE; i++)
		{
			int v = e[i].v;
			e[i].u = id[e[i].u];
			e[i].v = id[e[i].v];
			if(e[i].u != e[i].v) e[i].w -= in[v];
		}
		NV = cntnode;
		root = id[root];
	}
	return ret;
}

int main ()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        init();
        type ans = Directed_MST(0, n, m);
        if (ans == -1) puts("poor snoopy");
        else printf("%.2f
", ans);
    }
    return 0;
}