[题解] poj 3164 Command Network (朱刘算法最小树形图(有向生成树))

- 传送门 -

#Command Network

Description

After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.

With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.

Input

The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 10⁴), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair x_i and y_i, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.

Output

For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy’.

Sample Input

4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3

Sample Output

31.19
poor snoopy

[[Submit](http://poj.org/submit?problem_id=3164)] [[Status](http://poj.org/problemstatus?problem_id=3164)] [[Discuss](http://poj.org/bbs?problem_id=3164)]

- 题意 -

　有向图中的最小生成树.
　即最小树形图.
　(即在有向图中以一个特殊点root为根构造的一棵有向生成树, 边的方向由父亲指向儿子).
　

- 思路 -

　参考讲解:　 http://blog.csdn.net/chenzhenyu123456/article/details/47998315
　
　大致操作步骤如下:
　1. 扫一遍边, 对于每个节点(以x为例), 找到指向自己的边(入边)中权值最小的一个并记录该边权值IN[x],该边头结点PRE[x].
　2. 扫一遍点, 如果有非根节点没有1中找到的入边, 说明该点不能连入树中, 不存在最小树形图, 结束. 否则下一步.
　3. 此时我们得到了一棵可能有环的(非法)树, 先扫点, 对于每一个点(以 p 为例), 把它的IN[]值加给 ans , 我们找它在树上的祖先(视PRE[x] 为 x 树上的父节点), 同时每次查找我们都给找到的点打一个标记 VIS[x] = p (VIS[]可以区别本次查找到的点和之前查找的点).
　　　(mathit{1}) 如果我们在找一个节点祖先的过程中找到了根节点, 说明找到的这条路径上没有环;
　　　(mathit{2}) 如果找到了在本次查找过程中已出现过的点(VIS[x] == p) 说明本次查找出现了环;
　　　(mathit{3}) 如果找到了一个已知在环上的节点, 退出查找.(关于这一点下面会讲).
　　出现以上三种情况中任意一种即退出查找.
　　若出现第二种情况, 转第4步, 出现第 (mathit{1}) 或 (mathit{3}) 种情况则对下一个点重复本步骤.
　4. 对于找到的环上节点,我们用PRE[]数组遍历这个环并对环上节点打标记ID[], 表示该节点属于哪一个环, 这也解释了第3步的第(mathit{3})种情况是通过判断ID[]数组来判断一个节点是否已经在一个环上的.
　5. 记录本次扫点一共出现了几个环, 若没有找到一个环, 说明树成立, 返回 ans 值并结束, 否则下一步.
　6. 缩点处理环, 对于没有在环上的节点, 我们都给一个ID[]值. 把ID[]值相同的点视为一个点, 扫边, 把边的两端节点改为其ID[]值, 若两端节点ID[]值不同, 说明缩点后该边仍存在, 若接下来我们要加入这条边(设为x -> y)(即用这条边替代原来指向 y 的边), 则要先删去指向 y 的入边, 即 IN[y], 所以可以将该边的权值 w 改为 w - IN[y], 完成缩点.
　7. 更新节点数和根, 回到第1步.
　
　细节见代码.
　

- 代码 -

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef double db;
const int N = 105;
const int M = 1e4 + 5;
const int inf = 0x3f3f3f3f;

struct edge {
	int frm, to;
	db v;
}W[M];

int X[N], Y[N];
db IN[N];
int PRE[N], ID[N], VIS[N];
int n, m, sz;

db dtc(int a, int b) {
	return sqrt((X[a] - X[b]) * (X[a] - X[b]) * 1.0
						 + (Y[a] - Y[b]) * (Y[a] - Y[b]) * 1.0);
}

void add_edge(int x, int y) {
	W[++sz].frm = x; W[sz].to = y;
	W[sz].v = dtc(x, y);
}

db zhuliu(int rt) {
	db ans = 0;
	while (true) {
		for (int i = 1; i <= n; ++i)
			IN[i] = inf;
		for (int i = 1; i <= sz; ++i)
			if (W[i].to == W[i].frm) continue; //第一次是不会有这种情况的, 但是缩点后就有这种情况了
			else if (IN[W[i].to] > W[i].v) {
				PRE[W[i].to] = W[i].frm;
				IN[W[i].to] = W[i].v; //找指向自己权值最小的边
			}
		for (int i = 1; i <= n; ++i)
			if (i != rt && IN[i] == inf) return -1; // 不能构成树
		int cnt = 0;
		memset(ID, 0, sizeof (ID));
		memset(VIS, 0, sizeof (VIS));
		//ID数组的初始化要与cnt记录的环数相匹配, 这里ID用0初始化, 则cnt从1开始记录, 也可以用-1初始化, 让cnt从0开始记录
		//初始化要注意, 因为这里的节点是从1开始编号的, 所以VIS数组中不会出现0, 可以用0来初始化, 若节点是从0开始编号, 则VIS中会有0, 不能用0初始化
		IN[rt] = 0; //删去rt的入边
		for (int i = 1; i <= n; ++i) {
			ans += IN[i];
			int v = i;
			// ID[v]!=0表示找到了一个之前已知在环上的节点
			// v==rt标示找到了根
			// VIS[v]==i表示找到了一个本次查找已经找过的节点, 形成了环
			while (!ID[v] && v != rt && VIS[v] != i) {
				VIS[v] = i;
				v = PRE[v];
			}
			if (v != rt && !ID[v]) {
				ID[v] = ++cnt; //cnt从1开始记录
				for (int j = PRE[v]; j != v; j = PRE[j])
					ID[j] = cnt; //给同一环上的节点打一个标示所属环的标记
			}
		}
		if (!cnt) break; // 没有环, 树成立
		for (int i = 1; i <= n; ++i)
			if (!ID[i])
				ID[i] = ++cnt; // 缩点
		for (int i = 1; i <= m; ++i) {
			int x = W[i].frm , y = W[i].to;
			W[i].frm = ID[x]; W[i].to = ID[y];
			if (ID[x] != ID[y])
				W[i].v -= IN[y]; // 重新处理边
			// 这里有点难理解, 因为环被缩成了一个点, 而根又必定不在环上, 所以下一轮操作会给这个新点加入一个入边, 设这个入边原本指向环上一点x, 则加入这条经过处理的新边实际上相当于用它取代了原本指向x的老边, 环也就被拆开了
		}
		n = cnt;
		rt = ID[rt]; // 维护新的点数目和根
	}
	return ans;
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		sz = 0;
		for (int i = 1; i <= n; ++i)
			scanf("%d%d", &X[i], &Y[i]);
		for (int i = 1; i <= m; ++i) {
			int a, b;
			scanf("%d%d", &a, &b);
			if (a != b) add_edge(a, b); //读入数据顺便处理自环
		}
		db ans = zhuliu(1);
		if (ans == -1) printf("poor snoopy
");
		else printf("%.2lf
", ans);
	}
	return 0;
}

[题解] poj 3164 Command Network (朱刘算法 最小树形图(有向生成树))