最小树形图 Directed-MST - Chu-Liu Algorithm
Problem-POJ 3164
给定 n 个节点的坐标,m 条有向边
以 1 为根,找最小树形图。
Solution
使用朱刘算法求解。
大致流程:
- 找除 root 以外的 $in_i$,代表点 i 权值最小入边的权值。
- 判断是否有点孤立,若有,无解,退出。
- 找权值最小入边是否构成环。若不构成,则一定会到达根节点。将环标记。
- 将环缩点。假设新点为 new,则 new 的出边权值不变,对于 (u,v),v 在 new 中的边,W(u,v)-=in[v]。同时 ans 应当加上 new 的 $in_i$ 之和。
- 将新建的图重新回到步骤 1. 若当前图不存在环,则此为最小树形图。
细节请参考代码。
如果当前图并没有指定根,则新建一个虚点,向所有点连所有边权值之和 + 1 的权值的边。之后跑有根 DMST,最后答案减去这个权值就 OK 了。
Code
// Code by ajcxsu
// Problem: POJ Command Network
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int N=110;
struct Point {
double x,y;
double operator - (const Point &b) { return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)); }
} p[N];
struct Edge {
int a,b;
double w;
Edge(int a=0,int b=0,double w=0):a(a),b(b),w(w) {}
} e[N*N];
int num[N],pre[N]; // 新点的编号,前置点
double in[N]; // 前置点
int fa[N]; // 标记数组
#define EPS (1e-8)
int n,m;
double dmst(int root) {
double ret=0;
int u,v;
while(1) {
for(int i=1;i<=n;i++) in[i]=1e20; // 忽略了pre的重置
for(int i=0;i<m;i++) {
u=e[i].a, v=e[i].b;
if(in[v]-e[i].w>EPS && u!=v) { // 缩点过后编号可能相等
in[v]=e[i].w, pre[v]=u;
}
}
for(int i=1; i<=n;i++)
if(in[i]==1e20 && i!=root) return -1; // 判断有无孤立点
int idx=1;
in[root]=0;
CLR(num), CLR(fa); // 清空数组
for(int i=1; i<=n;i++) {
ret+=in[i]; // 由于把点也当做环,所以这个操作是必要的
v=i;
while(fa[v]!=i && !num[v] && v!=root) {
fa[v]=i;
v=pre[v];
} // 可能找到环,此时fa[v]==i;可能枚举的本来就是环,此时num[v]!=0;如果到达root,并非环,停止。
if(v!=root && !num[v]) { // 排除后两种情况
for(u=pre[v]; u!=v; u=pre[u]) num[u]=idx;
num[v]=idx++;
} // 标记环
}
if(idx==1) break; // 如果没有环,即已经找到最小树形图,退出。
for(int i=1;i<=n;i++)
if(!num[i]) num[i]=idx++; // 点的重编号
for(int i=0;i<m;i++) {
v=e[i].b;
e[i].a=num[e[i].a], e[i].b=num[e[i].b];
if(e[i].a != e[i].b) e[i].w-=in[v]; // 对于每个指向环内的点一视同仁
}
n=idx-1;
root=num[root]; // 更新点的个数和根节点的编号
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout<<setprecision(2);
while(cin>>n>>m) {
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
for(int i=0;i<m;i++) cin>>e[i].a>>e[i].b, e[i].w=p[e[i].a]-p[e[i].b];
double ans=dmst(1);
if(ans<0) cout<<"poor snoopy"<<endl;
else cout<<ans<<endl;
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/directed-mst.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆