朱刘算法求最小树形图

最近刷到一道题，题意是求有向图的最小生成树，一看题意就想用prime写，结果听取wa声一片，搜了一下题解才知道要用朱刘算法写。学了一下朱刘算法。
https://www.cnblogs.com/xzxl/p/7243466.html
学的时候，这篇博客的缩点部分看了好一会它的描述觉得好绕，其他的教程又一笔带过，在这里就补充一下自己的理解。

为什么prime会错呢？

朱刘算法求最小树形图
这张图用prime算得12，取的是a->b,b->c两条边，而答案是9，取a->c,c->b

朱刘算法过程：

对于当前的图，对于每一个点v，得到指向v的最小边权和它相应的前驱，如果存在一个点它没有前驱且它不是根结点，这张图就不存在最小树形图，直接返回-1。这个算法的算法过程如下：

for(int i = 0;i < m;++i){//m是边数
			int u,v;
			u = e[i].u;v = e[i].v;
			if(in[v] > e[i].w && u!=v) pre[v] = u,in[v] = e[i].w;//排除自环情况 
		}
		for(int i = 0;i < n;++i) if(i!=root && in[i] == inf) return -1;

完成步骤1后除了根结点每个点都有前驱了，图就被连起来了。在连好的图里找环，把在同一个环内的所有点做同一个标记。

for(int i = 0;i < n;++i) id[i] = vis[i] = -1;
		in[root] = 0; //根
		int tot = 0;//各个集团个数(环 or 点)
		for(int i = 0;i < n;++i){
			ans += in[i];
			int u,v;
			for(u = i;vis[u]!=i && id[u]==-1 && u!=root;u = pre[u]) vis[u] = i;
			//从i点往上找，有三种情况结束1.找到找过的点 2.找到别的环路 3.到根
			if(vis[u] == i){
				for(v = pre[u];v!=u;v = pre[v]) id[v] = tot;
				id[u] = tot++;
			}
		}
		if(tot == 0) break;//不存在环了，结束算法

进行缩点，把每个环的所有点映射到一个点。这时候要改指向环内点的边的权值，怎么更改呢？因为求的是树形图，之后肯定会在环内删除一条边，所以每条连到环内点v的边 i->v，都要减去v在环内指向它的边u->v，这样选了i->v的话就相当于删了u->v了。比如图中e->c要减去b->c的权值，d->b要减去a->b的权值。

for(int i = 0;i < n;++i) id[i] = vis[i] = -1;
		in[root] = 0; //根
		int tot = 0;//各个集团个数(环 or 点)
		for(int i = 0;i < n;++i){
			ans += in[i];
			int u,v;
			for(u = i;vis[u]!=i && id[u]==-1 && u!=root;u = pre[u]) vis[u] = i;
			//从i点往上找，有三种情况结束1.找到找过的点 2.找到别的环路 3.到根
			if(vis[u] == i){
				for(v = pre[u];v!=u;v = pre[v]) id[v] = tot;
				id[u] = tot++;
			}
		}
		if(tot == 0) break;//不存在环了，结束
		for(int i = 0;i < n;++i) if(id[i] == -1) id[i] = tot++;
		for(int i = 0;i < m;++i){//缩点 
			int u = e[i].u,v = e[i].v;
			e[i].u = id[u];e[i].v = id[v];
			if(e[i].u != e[i].v){
				e[i].w -= in[v];
			}
		}
		n = tot;
		root = id[root];

回到步骤1

完整代码：

POJ3164

#include<iostream>
#include<string.h>
#include<cmath>
#include<cstdio>
#define db double
using namespace std;
const int maxn = 1e3 + 50;
const db inf = 1e9;
struct node{
	int u,v;
	db w;
}e[maxn*maxn];
int vis[maxn],id[maxn],pre[maxn];
db in[maxn];
db x[maxn],y[maxn];
int n,m;
db cal(int i,int j){
	db ans = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
	ans = sqrt(ans);return ans;
}
void init(){
	for(int i = 0;i < n;++i) scanf("%lf%lf",&x[i],&y[i]);
	for(int i = 0;i < m;++i){
		int u,v;scanf("%d%d",&u,&v);
		e[i].u = u-1;e[i].v = v-1;e[i].w = cal(u-1,v-1);
	}
}
double zhiliu(int root){
	double ans = 0;
	while(1){
		for(int i = 0;i < n;++i) in[i] = inf;
		for(int i = 0;i < m;++i){
			int u,v;
			u = e[i].u;v = e[i].v;
			if(in[v] > e[i].w && u!=v) pre[v] = u,in[v] = e[i].w;//排除自环情况 
		}
		for(int i = 0;i < n;++i) if(i!=root && in[i] == inf) return -1;
		//除了根之外还有没前驱的孤立点 ，返回-1 
		//下面找有向环
		for(int i = 0;i < n;++i) id[i] = vis[i] = -1;
		in[root] = 0; //根
		int tot = 0;//各个集团个数(环 or 点)
		for(int i = 0;i < n;++i){
			ans += in[i];
			int u,v;
			for(u = i;vis[u]!=i && id[u]==-1 && u!=root;u = pre[u]) vis[u] = i;
			//从i点往上找，有三种情况结束1.找到找过的点 2.找到别的环路 3.到根
			if(vis[u] == i){
				for(v = pre[u];v!=u;v = pre[v]) id[v] = tot;
				id[u] = tot++;
			}
		}
		if(tot == 0) break;//不存在环了，结束
		for(int i = 0;i < n;++i) if(id[i] == -1) id[i] = tot++;
		for(int i = 0;i < m;++i){//缩点 
			int u = e[i].u,v = e[i].v;
			e[i].u = id[u];e[i].v = id[v];
			if(e[i].u != e[i].v){
				e[i].w -= in[v];
			}
		}
		n = tot;
		root = id[root];
	}
	return ans;
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		double ans = zhiliu(0);
		if(ans != -1) printf("%.2f\n",ans);
		else printf("poor snoopy\n");
	}
}

当根是不固定的时候，就设一个虚根，从这个虚根向每个点连一条很大的边（至少要比其他所有边加起来都大，因为要保证虚根的子节点只有一个。），然后就直接套模板吧。找实际根结点的时候只要记录用了哪条虚边就可以了。
hdu2121

#include<iostream>
#include<string.h>
#include<cmath>
#include<cstdio>
#define db double
#define ll long long 
using namespace std;
const int maxn = 1e3 + 50;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll sum;
struct node{
	int u,v;
	ll w;
}e[maxn*maxn];
int vis[maxn],id[maxn],pre[maxn];
ll in[maxn];
int n,m,tm;
void init(){
	sum = 0;
	for(int i = 0;i < m;++i){
		int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);
		e[i].u = u;e[i].v = v;e[i].w = w;
		sum+= w;
	}
	for(int i = m;i < m + n;++i){
		e[i].u = n;e[i].v = i - m;e[i].w = sum + 1;
	}
	tm = m;
	m = m + n;
	n++;
}
int pos;
ll zhiliu(int root){
	ll ans = 0;
	while(1){
		for(int i = 0;i < n;++i) in[i] = inf;
		for(int i = 0;i < m;++i){
			int u,v;
			u = e[i].u;v = e[i].v;
			if(in[v] > e[i].w && u!=v) {//排除自环情况
				pre[v] = u;in[v] = e[i].w;
				if(u == root) {
				pos = i;// 记录虚根连向答案的点所用的边 
				}
			} 
		}
		for(int i = 0;i < n;++i) if(i!=root && in[i] == inf) return -1;
		//除了根之外还有没前驱的孤立点 ，返回-1 
		//下面找有向环
		for(int i = 0;i < n;++i) id[i] = vis[i] = -1;
		in[root] = 0; //根
		int tot = 0;//各个集团个数(环 or 点)
		for(int i = 0;i < n;++i){
			ans += in[i];
			int u,v;
			for(u = i;vis[u]!=i && id[u]==-1 && u!=root;u = pre[u]) vis[u] = i;
			//从i点往上找，有三种情况结束1.找到找过的点 2.找到别的环路 3.到根
			if(vis[u] == i){
				for(v = pre[u];v!=u;v = pre[v]) id[v] = tot;
				id[u] = tot++;
			}
		}
		if(tot == 0) break;//不存在环了，结束
		for(int i = 0;i < n;++i) if(id[i] == -1) id[i] = tot++;
		for(int i = 0;i < m;++i){//缩点 
			int u = e[i].u,v = e[i].v;
			e[i].u = id[u];e[i].v = id[v];
			if(e[i].u != e[i].v){
				e[i].w -= in[v];
			}
		}
		n = tot;
		root = id[root];
	}
	return ans;
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		ll ans = zhiliu(n-1);
		if(ans >= 2*sum + 2) cout<<"impossible\n\n";
		else {
			//cout<<pos<<endl;
			printf("%lld %d\n\n",ans-sum - 1,pos - tm);
		}
	}
}

朱刘算法求最小树形图

为什么prime会错呢？

朱刘算法过程：

完整代码：

相关推荐