POJ3164 Command Network(最小树形图)

图论填个小坑。以前就一直在想，无向图有最小生成树，那么有向图是不是也有最小生成树呢，想不到还真的有，叫做最小树形图，网上的介绍有很多，感觉下面这个博客介绍的靠谱点：

http://www.cnblogs.com/vongang/archive/2012/07/18/2596851.html

所以下面的代码也是抄上面的模板的。里面还给出了不定根情况下的最小树形图的做法，新增一个虚拟根，连向其它所有点的费用是总费用＋1，然后跑一次算法就可以了，这样可以保证虚拟根一定连出去某个顶点，而且不可能连两个，最后跑出来把多的费用减掉就可以了。感觉想法挺神奇的。

#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

#define maxn 120
#define maxm 12000

int n, m;

struct Edge{
	int u, v;
	double w;
	Edge(int ui, int vi, double wi) :u(ui), v(vi), w(wi){}
	Edge(){}
};

vector<Edge> E;

double x[maxn], y[maxn];

double dist(int i, int j){
	return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}

double in[maxn]; // minimum pre edge weight
int pre[maxn]; // pre vertex
int vis[maxn]; // vis array
int id[maxn]; // mark down the id
int nv; // nv is the number of vertex after shrinking

double directed_mst(int root)
{
	double ret = 0; int nv = n;
	while (1){
		for (int i = 0; i < nv; ++i) in[i] = 1e10;
		for (int i = 0; i < m; ++i){
			int u = E[i].u, v = E[i].v;
			if (E[i].w < in[v] && u != v){
				in[v] = E[i].w;
				pre[v] = u;
			}
		}
		// found not connected means impossible
		for (int i = 0; i < nv; ++i){
			if (i == root) continue;
			if (in[i]>1e9) 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){
			ret += in[i];
			int v = i;

			while (vis[v] != i&&id[v] == -1 && v != root){
				vis[v] = i;
				v = pre[v];
			}
			// v!=root means we find a circle,id[v]==-1 guarantee that it's not shrinked.
			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++;
		}
		// change the cost of edge for each (u,v,w)->(u,v,w-in[v])
		for (int i = 0; i < m; ++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];
		}
		// mark down the new root
		root = id[root];
		// mark down the new vertex number
		nv = cnt;
	}
	return ret;
}

int main()
{
	while (cin >> n >> m){
		E.clear();
		for (int i = 0; i < n; ++i){
			scanf("%lf%lf", x + i, y + i);
		}
		int ui, vi;
		for (int i = 0; i < m; ++i){
			scanf("%d%d", &ui, &vi);
			--ui; --vi;
			if (ui != vi) E.push_back(Edge(ui, vi, dist(ui,vi)));
		}
		m = E.size();
		double ans = directed_mst(0);
		if (ans < 0) puts("poor snoopy");
		else printf("%.2f
", ans);
	}
	return 0;
}