POJ 3164 朱刘算法详细解释(最小树形图)

POJ 3164

  • 最小树形图就是有向图的最小生成树
  • 题意:给出n个点,m条边.求有向图的最小生成树

    题目数据处理

  1. 消除图中的自环(自己指向自己的边).改成INF
  2. 存点存边

    朱刘算法原理

  3. 首先判断有向图的最小生成树是否存在
    1. dfs (场合不合适)
    2. 先判断除根节点外每个点是否有入边,没有入边也不能组成最小生成树.顺便维护除根节点外每个点的的最小入边(最小树形图的边集)
  4. 选出的所有点(除去根节点)的最小入边组成了最小树形图的边集.
  5. 如果有向图中中某些点组成了有向环.那么来缩点，ans是最小树形图的路径和(边集和)
    eLiXUH.png
    eLFiqS.png
  • 上图是该图的最小树形图,此时ans=9+7+6
  • 无论4->2的边权有多小或多大,都要舍弃,因为边是有方向的,优先满足能够组成最小树形图

    把环缩成点的精髓其实是为了方便统计ans

    eLFYGR.png
  • 缩点时ans+=有向环的所有边的边权.但是我们又不需要4->2这条边,暂时加入到ans中,等会通过边集把它减去,1->2的权值=6-8=-2,因为点2的最小入边一定会在最小树形图中(新图中作为缩点的入边),那么此边也会统计到ans中,作为新图的缩点的入边
  • 缩点的出边是有向环上任意一点到环外点的所有边中的最小值

    建立新图,直到不存在有向环时,最小树形图就找到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
const int maxn = 205;
const double inf = 1.0 * 0x3f3f3f3f;
struct point {
	double x, y;
}p[maxn];
struct node {
	int u, v;
	double w;
}edge[maxn * maxn];
int pre[maxn], id[maxn], vis[maxn], n, m;
double in[maxn];
double getdis(point a,point b) {
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
double mst(int root,int nn,int mm) {
	double res = 0;
	while (1) {
		for (int i = 0; i < nn; i++) in[i] = inf; //每个点的最小入边初始化为inf
		for (int i = 0; i < mm; i++) {
			int u = edge[i].u, v = edge[i].v;
			if (edge[i].w < in[v] && u != v) { //不是自环,初始化每个点的入边最小值,和上一个点
				pre[v] = u; 
				in[v] = edge[i].w;
			}
		}
		for (int i = 0; i < nn; 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 < nn; i++) {//一直找每个点的前一个点,缩点、标记点来建立新图
			res += 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;
		//有的点没有新id,比如根节点
		for (int i = 0; i < nn; i++) if (id[i] == -1) id[i] = cnt++;
		for (int i = 0; i < mm; i++) {
			int u = edge[i].u, v = edge[i].v;
			edge[i].u = id[u];
			edge[i].v = id[v];
			if (id[u] != id[v]) edge[i].w -= in[v];
		}
		nn = cnt;
		root = id[root];
	}
	return res;
}
int main() {
//	freopen("a.txt","r",stdin);
	while (scanf("%d%d",&n,&m) != EOF) {
		for (int i = 0; i < n; i++) scanf("%lf%lf",&p[i].x,&p[i].y);
		for (int i = 0; i < m; i++) { //m条有向边
			scanf("%d%d",&edge[i].u,&edge[i].v);
			edge[i].u--; edge[i].v--;
			if (edge[i].u != edge[i].v) edge[i].w = getdis(p[edge[i].u], p[edge[i].v]);
			else edge[i].w = inf;//2个顶点相同,自环的距离是无穷
		}
		double ans = mst(0,n,m);
		if (ans == -1) printf("poor snoopy\n");
		else printf("%.2f\n",ans);
	}
	return 0;
}