最小树形图 Directed-MST - Chu-Liu Algorithm

Problem-POJ 3164

给定n个节点的坐标,m条有向边
以1为根,找最小树形图。

Solution

使用朱刘算法求解。
大致流程:

  1. 找除root以外的$in_i$,代表点i权值最小入边的权值。
  2. 判断是否有点孤立,若有,无解,退出。
  3. 找权值最小入边是否构成环。若不构成,则一定会到达根节点。将环标记。
  4. 将环缩点。假设新点为new,则new的出边权值不变,对于(u,v),v在new中的边,W(u,v)-=in[v]。同时ans应当加上new的$in_i$之和。
  5. 将新建的图重新回到步骤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://acxblog.site/archives/directed-mst.html
本文采用 CC BY-NC-SA 3.0 协议进行许可