最小樹形図【poj 3164 Command Network】

定義:図の最小生成ツリーがある.
アルゴリズムプロセス:最小生成ツリーと同じですが、これは無方向図ではありませんが、同様のアルゴリズムで最小樹形図の最初のアルゴリズム数朱劉アルゴリズムを用いて、最小生成樹数アルゴリズムに基づいて形成されます.
最小生成ツリーアルゴリズムでは、最長の辺を選ぶたびに、条件を満たすと最小生成ツリーに参加し、すべての点がツリーの中にあることを知っています.最小樹形図は同じです.
まず最小生成ツリーと同じように、まず図の連結を保証しなければなりません.さもなければ、最小樹形図を形成することができません.
しかし、方向があるので、すべての点の中で一番小さい端に入るのとこの図の最小樹形図を探していますが、肝心なところは環を形成する可能性があります.私達がやるべきのは収縮点です.リングが形成されているところを縮めて、環の中に入るとdis-in【u】になります.disはもとのリングまでの距離です.リング上の点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
",ans);
        e.clear();
    }
    return 0;
}