This is not the end.

0%

朱刘算法

Posted on

这个算法用于求解有向图的最小树形图问题。

树形图：图中有一个点作为根，除了根以外，每个点的入度恰好为$1$，并且从根出发可以到达整个图中的任意一个点。

最小树形图就是所有边的边权和最小的树形图。

算法流程

1）对于图中所有的不为根的点，我们钦定图中连向它的、边权最小的边，作为它的入边。设由所有点以及我们钦定的入边构成的图为$G’$。
2）如果$G’$中不存在环，那么$G’$就是我们要的最小树形图。否则，我们直接把环上的点缩成一个点。把$G’$中，所有边的边权修改为：这条边原来的边权 - 我们在第一步中给这条边的终点钦定的边的边权（这一步相当于是给这个贪心一个反悔的机会）。然后重复1），直到图中没有环。

我们最后得到的那个最小树形图，上面的边一定都在原图的最小树形图中。我们找出这张图上我们缩的点，把他们展开，并保留与终点在最终的图中没有入度的边。这样就可以得到原图的最小树形图。

复杂度分析

每一次执行2）的时候，我们至少会让图中的点数$-1$，因此我们至多会执行$n$次1）2）。考虑到1）2)的复杂度是$O(n+m)$的，其中$m$大于$n$，所以我们的总复杂度是$O(nm)$的。

模板

poj3164

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
80
81
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define db long double 
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=110,M=10010;
struct Point {
	db x,y;
	Point(db x=0,db y=0): x(x),y(y) {}
	friend Point operator -(Point A,Point B) { return Point(A.x-B.x,A.y-B.y); }
	db dis() { return sqrt(x*x+y*y); }
}p[N];
struct ed{int u,v; db w;}E[M];
int vis[N],pre[N],bel[N],n,m,rt;
db cost[N];
void DMST(int n,int m,int rt) {
	db ans=0;
	while(true) {
		for(int i=1;i<=n;++i) vis[i]=0,pre[i]=-1,cost[i]=1e100,bel[i]=-1;
		for(int i=1;i<=m;++i) {
			if(E[i].v==rt) continue;
			if(E[i].u==E[i].v) continue;
			if(cost[E[i].v]>E[i].w)
				cost[E[i].v]=E[i].w,pre[E[i].v]=E[i].u;
		}
		for(int i=1;i<=n;++i) {
			if(i==rt) continue;
			if(pre[i]==-1) {
				printf("poor snoopy\n");
				return;
			}
			ans+=cost[i];
		}
//		cout<<rt<<endl;
//		for(int i=1;i<=n;++i) cout<<i<<' '<<pre[i]<<endl;
		
		int cnt=0;
		for(int i=1,v,x;i<=n;++i) if(i!=rt&&!vis[i]) {
			vis[i]=i;
			for(v=pre[i];!vis[v]&&v!=rt;v=pre[v])
				vis[v]=i;
			if(vis[v]!=i) continue;
			++cnt; bel[v]=cnt;
			for(x=pre[v];x!=v;x=pre[x]) bel[x]=cnt;
		}
		if(cnt==0) break; 
		for(int i=1;i<=n;++i) if(bel[i]==-1) bel[i]=++cnt;
		for(int i=1;i<=m;++i) {
			while(i<=m&&bel[E[i].u]==bel[E[i].v]) {
				swap(E[i],E[m]),m--;
			}
			if(i>m) break;
			E[i].w-=cost[E[i].v];
			E[i].u=bel[E[i].u],E[i].v=bel[E[i].v];
		}
		n=cnt,rt=bel[rt];
	}
	printf("%.2Lf\n",ans);
}
int main() {
	while(~scanf("%d%d",&n,&m)) {
		rt=1;
		for(int i=1;i<=n;++i) scanf("%Lf%Lf",&p[i].x,&p[i].y);
		for(int i=1;i<=m;++i) {
			scanf("%d%d",&E[i].u,&E[i].v);
			E[i].w=(p[E[i].u]-p[E[i].v]).dis();
		}
		DMST(n,m,rt);
	}
	return 0;
}