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;
}