POJ 3164 Command Network(最小ツリー図)

タイトルタイプ最小ツリー図
タイトルの意味
最大100個の点と10000個の有向辺を与えて、1から出発する最小有向生成ツリーの重み値はいくらですかを聞きます
解題方法
最小ツリーグラフ->Chu-Liu/Edmonds Algorithm(一番下)
参考コード-疑問点がある場合は下記のメッセージを見てすぐに返事します

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 100 + 10;
const int INF = 1<<29;

struct Edge {
	int u, v;
	double cost;
}E[maxn*maxn];

struct Point {
	double x, y;
}point[maxn];

double sq(int u, int v) {
	double x = point[u].x - point[v].x;
	double y = point[u].y - point[v].y;
	return sqrt(x*x + y*y);
}

struct DM {
	int NV, NE;
	double in[maxn];
	int id[maxn], vis[maxn], pre[maxn];

	void init(int nv, int ne) {
		NV = nv, NE = ne;
	}
	double Directed_MST(int root) {
		double ans = 0;
		while(true) {
			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].cost < in[v] && u != v) {
					in[v] = E[i].cost;
					pre[v] = u;
				}
			}
			for( int i=0; i<NV; i++ ) {
				if(i == root) continue;
				if(in[i] == INF) return -1;
			}

			int cnt = 0;
			memset(id, -1, sizeof(id));
			memset(vis, -1, sizeof(vis));
			in[root] = 0;

			for( int i=0; i<NV; i++ ) {
				ans += 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] = cnt;
					}
					id[v] = cnt++;
				}
			}
			if(cnt == 0) break;
			for( int i=0; i<NV; i++ ) {
				if(id[i] == -1) id[i] = cnt++;
			}
			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].cost -= in[v];
				}
			}
			NV = cnt;
			root = id[root];
		}
		return ans;
	}
}dm;

int main() {
	freopen("in", "r", stdin);
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF) {
		for( int i=0; i<n; i++ ) scanf("%lf%lf", &point[i].x, &point[i].y);
		for( int i=0; i<m; i++ ) {
			scanf("%d%d", &E[i].u, &E[i].v);
			E[i].u--, E[i].v--;
			E[i].cost = sq(E[i].u, E[i].v);
		}
		dm.init(n, m);
		double ans = dm.Directed_MST(0);
		if(ans == -1) printf("poor snoopy
");
		else printf("%.2f
", ans);
	}		
	return 0;
}