POJ 3164 Command Network(Minimum tree-shape graph)

Description

N个点M条有向边，求以1位根节点最小树形图(有向最小生成树)

朱刘算法

①选出入边集：找到除root点之外，每一个点的所有入边中权值最小的，用数组in[]记录下这个最小权值，用pre[]记录到达该点的前驱。判断是否存在无入边的点(除了root)，若有，则无法成树。

②找有向环：倘若无环，则该入边集就是最小树形图，算法结束。

若有环，说明未成树，做缩点前期工作：记下环上每个点所属环的标号。

③缩点中期工作：将不属于环上的点“缩点”

④缩点后期工作：更新缩点后的图中的边的权值。因为我们在过程中“误+”了环中某一边，此时要减掉。重复以上过程。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;

int n, m, id[N], pre[N], vis[N];
double x[N], y[N], in[N];

struct edge
{
    int u, v;
    double w;
}e[4 * N * N];

double getDis(double x, double y, double xx, double yy)
{
    return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}

double zhuliu(int root)
{
    int u, v;
    double res = 0;
    while(true)
    {
        ///①.Set of in
        for(int i = 1; i <= n; ++i)
            in[i] = -1.0;
        for(int i = 1; i <= m; ++i)
            if(e[i].u != e[i].v && (e[i].w < in[ e[i].v ] || in[ e[i].v ] < 0))
                in[ e[i].v ] = e[i].w, pre[ e[i].v ] = e[i].u;
        for(int i = 1; i <= n; ++i)
            if(i != root && in[i] < 0)
                return -1.0;

        ///②.Directed circle
        int cnt = 1;
        memset(id, -1, sizeof(id));
        memset(vis,-1, sizeof(vis));
        in[root] = 0;
        for(int i = 1; i <= n; ++i)
        {
            res += in[i];
            v = i;
            while(id[v] == -1 && v != root && vis[v] != i)
                vis[v] = i, v = pre[v];
            if(id[v] == -1 && v != root)///   vis[v] == i
            {
                for(u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }

        ///③.No circle -> Over
        if(cnt == 1)
            break;

        ///④.Process other nodes ,and then "shrink".
        for(int i = 1; i <= n; ++i)
            if(id[i] == -1)
                id[i] = cnt++;
        for(int i = 1; i <= m; ++i)
        {
            v = e[i].v;
            e[i].u = id[ e[i].u ];
            e[i].v = id[ e[i].v ];
            if(e[i].u != e[i].v)
                e[i].w -= in[v];///This v is the original v!
        }
        n = cnt - 1;
        root = id[root];
    }
    return res;
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        for(int i = 1; i <= n; ++i)
            scanf("%lf %lf", &x[i], &y[i]);
        int u, v;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d", &u, &v);
            e[i].u = u, e[i].v = v;
            e[i].w = getDis(x[u], y[u], x[v], y[v]);
        }
        double ans = zhuliu(1);
        if(ans < 0)
            cout << "poor snoopy" << '\n';
        else
            printf("%.2f\n", ans);
    }
}