데이터 구조 실험의 도 론 6: 촌 촌 통 도로

데이터 구조 실험의 도 론 6: 촌 촌 통 도로
Time Limit: 1000 ms Memory Limit: 65536 KiB
 
Problem Description
현재 농촌 도로 건설 이 활발 하 게 진행 되 고 있 습 니 다. 한 향 진 정 부 는 마을 과 마을 의 도 로 를 실현 하기 로 결 정 했 습 니 다. 엔 지 니 어 는 현재 각 마을 간 의 원시 도로 통계 데이터 표 에 각 마을 간 에 도 로 를 건설 할 수 있 는 몇 가지 도로 의 원 가 를 표 시 했 습 니 다. 당신 의 임 무 는 제 시 된 데이터 표 에 근거 하여 모든 마을 이 도로 연결 에 필요 한 최저 원 가 를 가지 도록 하 는 것 입 니 다.
Input
여러 조 의 데 이 터 를 연속 으로 입력 하면 각 조 의 데 이 터 는 마을 수 N (N < = 1000) 과 선택 할 수 있 는 도로 수 M (M < = 3000) 을 포함한다. 그 다음 에 M 행 은 M 개의 도로 에 대응 하고 각 줄 은 3 개의 정 수 를 제시한다. 각각 이 도로 가 직접 연 결 된 두 마을 의 번호 와 이 도 로 를 건설 하 는 예산 비용 이 고 마을 은 1 ～ N 번호 이다. 
Output
수출 은 모든 마을 로 하여 금 도로 연결 에 필요 한 최저 비용 을 가지 게 한다. 만약 에 데 이 터 를 입력 하여 모든 마을 을 원활 하 게 하지 못 하면 수출 - 1 은 일부 마을 간 에 도로 연결 이 없다 는 것 을 나타 낸다. 
Sample Input

5 8
1 2 12
1 3 9
1 4 11
1 5 3
2 3 6
2 4 9
3 4 4
4 5 6

Sample Output

19

 

/***************************
    Kruskal     
***************************/
#include
#include
#include
using namespace std;

struct node
{
    int u;
    int v;
    int w;

}edge[3001];//    

int f[3001];

void sqort(struct node edge[], int l, int r)
{
    int i, j;
    struct node key;
    if(l >= r)
    {
        return ;
    }

    key = edge[l];
    i = l;
    j = r;

    while(i < j)
    {
        while(i < j && edge[j].w >= key.w)
        {
            j--;
        }
        edge[i] = edge[j];
        while(i < j && edge[i].w <= key.w)
        {
            i++;
        }

        edge[j] = edge[i];
    }

    edge[j] = key;

    //   
    sqort(edge, l, j - 1);
    sqort(edge, j + 1, r);

}

//findx   unionx        CSDN      ，      
//https://blog.csdn.net/Eider1998/article/details/83589845
int findx(int x)
{
    if(f[x] == x)
    {
        return x;
    }

    else
    {
        f[x] = findx(f[x]);
    }

    return f[x];
}

int unionx(int x, int y)
{
    int t1 = findx(x), t2 = findx(y);

    if(t1 != t2)
    {
        f[t2] = t1; // t2     t1;
        return 1;
    }

    else //  t1,t2                          
    {
        return 0;
    }
}

int main(void)
{
    int n, m, i, sum;
    int countx;

    while(~scanf("%d %d", &n, &m))
    {
        memset(f, 0, sizeof(f));
        countx = 0;
        sum = 0;
        for(i = 1; i <= n; i++)
        {
            f[i] = i;//       n-1        
        }
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
        }

        //    ,              
        sqort(edge, 1, m);


        //  findx   unionx    n-1  ，         
        for(i = 1; i <= m; i++)
        {
            if(unionx(edge[i].u, edge[i].v))//         
            {
                countx++;
                sum += edge[i].w;
            }

            if(countx == n - 1)
            {
                printf("%d
", sum);
                break;
            }
        }

        if(countx != n - 1)
        {
            printf("-1
");
        }

    }

    return 0;
}