zoj - 1203 - Swordfish

タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1203
标题:n都市を結ぶ最短経路を求める.
——>>まず「任意」の2点間の距離をdist配列に格納し、それを並べ替え、distのスキャンを開始します.
スキャンした2つの点の木の根が同じであれば、この2つの都市がつながっていることを示し、距離を置く必要はありません.スキャンした2つの点の木の根が異なる場合、
この2つの都市がまだつながっていないことを説明します.sumはこの距離を加えて、最後にsumを出力すればいいです.
パス圧縮:

#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 100 + 10;      //   100   

typedef struct Tnode        //     
{
    double x;
    double y;
}node;

typedef struct Tdistance        //      ，       map[n1]  map[n2]     
{
    int n1;
    int n2;
    double dis;
}cdis;

bool cmp(cdis d1, cdis d2)      //      ，           
{
    return d1.dis < d2.dis;
}

int fa[maxn];     //fa      ，height      

int find(int x)     //    x  （ map    ）
{
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

bool judge(int x, int y)        //  、    
{
    int new_x = find(x);
    int new_y = find(y);
    if(new_x == new_y) return 1;     //     x    y          ，  1，          
    fa[new_y] = new_x;
    return 0;
}

int main()
{
    int N, i, j;
    node map[maxn];      //   N   （N      ）
    cdis dist[maxn*maxn];     //           
    int cnt = 1, first = 1;     //cnt          ，first     
    while(cin>>N)
    {
        if(N == 0)  return 0;       // N 0 ，  

        for(i = 0; i < N; i++)      //  N     ，  map 
            cin>>map[i].x>>map[i].y;

        int m = 0;      //m             （ map[i] map[j]     ，   map[j] map[i]     ）
        for(i = 0; i < N; i++)
            for(j = i+1; j < N; j++)
            {
                dist[m].n1 = i;     //     map[i]   
                dist[m].n2 = j;     //     map[j]   
                dist[m++].dis = sqrt(pow(map[i].x - map[j].x, 2) + pow(map[i].y - map[j].y, 2));        //        
            }
        sort(dist, dist+m, cmp);        //  
        for(i = 0; i < N; i++)  fa[i] = i;      // N   ,         
        double sum = 0;     //         
        for(i = 0; i < m; i++)      // m       
        {
            int ok = judge(dist[i].n1, dist[i].n2);     //              
            if(!ok)     //           ，          ，    
                sum += dist[i].dis;
        }
        if(first) first = !first;       //           ，           
        else    cout<

小さな書き方がわかりやすい:

#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 100 + 10;      //   100   

typedef struct Tnode        //     
{
    double x;
    double y;
}node;

typedef struct Tdistance        //      ，       map[n1]  map[n2]     
{
    int n1;
    int n2;
    double dis;
}cdis;

bool cmp(cdis d1, cdis d2)      //      ，           
{
    return d1.dis < d2.dis;
}

int fa[maxn], height[maxn];     //fa      ，height      

int find(int x)     //    x  （ map    ）
{
    while(fa[x] != x)
    {
        x = fa[x];
    }
    return x;
}

bool judge(int x, int y)        //  、    
{
    int fx = find(x);
    int fy = find(y);

    if(fx == fy)        //     x    y          ，  1，          
        return 1;
    else        //  
    {
        if(height[fx] > height[fy])     //    x         >   y          
            fa[fy] = fx;        // fx  fy   
        else if(height[fx] == height[fy])       //    x         ==   y          
        {
            fa[fy] = fx;        // fx  fy   
            height[fx]++;       //    fx   +1
        }
        else        //    x         >N)
    {
        if(N == 0)  return 0;       // N 0 ，  

        for(i = 0; i < N; i++)      //  N     ，  map 
            cin>>map[i].x>>map[i].y;

        int m = 0;      //m             （ map[i] map[j]     ，   map[j] map[i]     ）
        for(i = 0; i < N; i++)
            for(j = i+1; j < N; j++)
            {
                dist[m].n1 = i;     //     map[i]   
                dist[m].n2 = j;     //     map[j]   
                dist[m++].dis = sqrt(pow(map[i].x - map[j].x, 2) + pow(map[i].y - map[j].y, 2));        //        
            }

        sort(dist, dist+m, cmp);        //  

        for(i = 0; i < N; i++)      // N   
        {
            fa[i] = i;      //         
            height[i] = 1;      //      1（       ）
        }

        double sum = 0;     //         

        for(i = 0; i < m; i++)      // m       
        {
            int ok = judge(dist[i].n1, dist[i].n2);     //              
            if(!ok)     //           ，          ，    
                sum += dist[i].dis;
        }
        if(first) first = !first;       //           ，           
        else    cout<