最小树形图【poj 3164 Command Network】

冷不防 2022-08-13 14:00 85阅读 0赞

定义：在有向图上的最小生成树。

算法过程：和最小生成树一样，不过这个不是无向图的，但是也可以用类似的算法，最小树形图的第一个算法数朱刘算法，依据最小生成树数算法形成的。

我们知道，在最小生成树算法中，我们每次选长度最短的边，如果满足条件则加入最小生成树中，知道所有的点都在树中，最小树形图同样。

首先和最小生成树一样，首先必须保证图联通，否则不能形成最小树形图。

但是由于是有向的，而我们只要找所有点的入边中最小的入边的和就是这个图的最小树形图，但是最关键的地方在于可能形成环，我们要做的就是缩点，把形成环的地方缩点，然后所有到环上的入边变为dis - in【u】，dis为原来边到环的距离，in【u】环上的点u的最小入边。而出边则不边，这样一直缩点，知道不存在环，所有入边的最小值和就是最小树形图的答案。

以poj 3164 Command Network 贴一个模板（注意VC编译了C++提交才能过）

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <math.h>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const int N = 110;
    const int inf = 0x3f3f3f3f;
    int n,m;
    struct Node
    {
        double x,y;
    };
    Node p[N];
    struct Tree
    {
        int from,to;
        double dis;
    };
    vector<Tree> e;
    double dis(Node a,Node b)
    {
        return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
    }
    int ha[N],vis[N],father[N];
    double in[N];
    double zhuliu(int root)
    {
        double ans = 0;
        while(true)
        {
            for(int i=0;i<n;i++)
                in[i] = inf;
            memset(father,-1,sizeof(father));
            for(int i=0; i<e.size(); i++) //找最小入边
            {
                int to = e[i].to;
                if(e[i].dis<in[to] && e[i].from!=e[i].to)
                {
                    in[to] = e[i].dis;
                    father[to] = e[i].from;
                }
            }
            for(int i=0;i<n;i++)
            {//printf("%.2lf ",in[i]);
                if(i!=root && in[i]==inf)
                    return -1;
            }
            int cnt = 0;
            in[root] = 0;
            memset(ha,-1,sizeof(ha));
            memset(vis,-1,sizeof(vis));
            for(int i=0;i<n;i++) //找自环
            {
    
                ans += in[i];
                int v = i;
                while(v!=root && ha[v]==-1 && vis[v]!=i)
                {
                    vis[v] = i;
                    v = father[v];
                }
                if(v!=root && ha[v]==-1)
                {
                    for(int j = father[v];j != v;j=father[j])
                    {
                        ha[j] = cnt;
                    }
                    ha[v] = cnt++;
                }
            }
            if(cnt == 0) //跳出条件
                break;
            for(int i=0;i<n;i++)
                if(ha[i]==-1)
                    ha[i]=cnt++;
            for(int i = 0; i< e.size();i++)
            {
                int tmp = e[i].to;
                e[i].from = ha[e[i].from];
                e[i].to = ha[e[i].to];
                if(e[i].from != e[i].to)
                    e[i].dis -= in[tmp];
            }
            n = cnt;
            root = ha[root];
        }
        return ans;
    }
    int main()
    {
        freopen("Input.txt","r",stdin);
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0; i<n; i++)
            {
                scanf("%lf%lf",&p[i].x,&p[i].y);
            }
            for(int i=0; i<m; i++)
            {
                int from,to;
                scanf("%d%d",&from,&to);
                if(from==to)
                    continue;
                from--,to--;
                double tmp = dis(p[from],p[to]);
                printf("%.2lf ",tmp);
                e.push_back((Tree){from,to,tmp} );
            }
            double ans = zhuliu(0);
            if(ans==-1)
                puts("poor snoopy");
            else
                printf("%.2lf\n",ans);
            e.clear();
        }
        return 0;
    }