ACM-매 끄 러 운 최소 생 성 트 리 프로젝트-hdu 1863

*************************************************************************
원활 한 프로젝트
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15572    Accepted Submission(s): 6462
Problem Description
성 정부의'원활 한 프로젝트'목 표 는 성 전체 가 어떤 두 마을 간 에 도 도로 교통 을 실현 할 수 있 도록 하 는 것 이다(그러나 반드시 직접적인 도로 가 연결 되 어 있 는 것 은 아니다.도 로 를 간접 적 으로 통과 할 수 있 기만 하면 된다.조사 평 가 를 거치다.얻 은 통계 표 에는 도 로 를 건설 할 수 있 는 몇 개의 도로 비용 이 열거 되 어 있다.
지금 당신 이 코드 를 짜 서 전 성의 원활 한 소통 에 필요 한 최저 원 가 를 계산 해 주 십시오.
 
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 줄 에 평 가 된 도로 개수 N,마을 수 M(<100)을 제시 합 니 다.다음 N 
해당 마을 간 도로 의 비용 을 지불 하 다.각 줄 은 한 쌍 의 정 수 를 주 고 각각 두 마을 의 번호 와 이 두 마을 간 도로 의 원가(정수)를 제시한다.
간단하게 말하자면,마을 은 1 부터 M 까지 번호 가 있다.N 이 0 일 때 모든 입력 이 끝나 면 해당 결 과 는 출력 하지 마 십시오.
 
Output
모든 테스트 용례.한 줄 에서 성 전체 가 원활 하 게 통 하 는 데 필요 한 최저 원 가 를 수출 하 다.통계 데이터 가 원활 함 을 보장 하지 못 하면 출력"?"
 
Sample Input

   

    3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
   

 
Sample Output

   

    3
?
    
    
   

 
Source
http://blog.csdn.net/lttree
 
제목:절 대 컴퓨터 대학원 재시험
최소 생 성 트 리 의 기본 제목 입 니 다.원활 한 프로젝트.
적나라한 최소 생 성 나무.
최소 생 성 트 리 가 될 수 있 을 지 추정 하기 위해 추가 로 추가 되 었 습 니 다.
이번에 내 가 사용 한 Kruskal 알고리즘.
Kruskal 빌 드 최소 생 성 트 리:
대체바로 가장 자 리 를 따라 정렬 하 는 것 이다(작은 것 부터 큰 것 까지).
그리고 바깥쪽 으로.
가 변 할 때 회 로 를 구성 할 수 있 는 지 를 추정 하고 회 로 를 구성 할 수 있다 고 가정 하면 가 변 을 할 수 없다.
왜 이렇게 하 는 것 이 옳 습 니까?
우선최소 생 성 트 리 는 회로 가 나타 나 지 않 는 다 는 것 을 알 아야 한다!
Why？혼자 계산 해.o(╯□╰)o。。。
그리고 우 리 는 작은 것 부터 큰 것 까지 순 서 를 매 겼 기 때문에 이렇게 가 하면 가장 작은 생 성 나 무 를 얻 을 수 있 습 니 다~
Kruskal 알고리즘 은 회 로 를 추정 하 는 것 이 중요 합 니 다.
이것 은 집합 으로 이 루어 진 것 입 니 다.
그리고마지막 으로 Find 함 수 를 찾 아 보 세 요.모든 점 이 같은 집합 에 있 습 니까?없 으 면 출력 합 니까?
응,오케이~

/****************************************
*****************************************
*        Author:Tree                    *
*From :http://blog.csdn.net/lttree      *
* Title :   project                     *
*Source: hdu 1863                       *
* Hint  :      （Kruskal）        *
*****************************************
****************************************/

#include <stdio.h>
#include <algorithm>
using namespace std;
struct EDGE
{
    int u,v,cost;
}eg[100001];
int n,m,father[100001];

bool cmp(EDGE e1,EDGE e2)
{
    return e1.cost<e2.cost;
}

//          
void Init( int m )
{
    int i;
    for(i=1;i<=m;i++)
        father[i]=i;
}
//         
int Find(int x)
{
    while(father[x]!=x)
        x=father[x];
    return x;
}
//         
void Combine(int a,int b)
{
    int temp_a,temp_b;
    temp_a=Find(a);
    temp_b=Find(b);

    if(temp_a!=temp_b)
        father[temp_a]=temp_b;
}

//       Kruskal   
int Kruskal( void )
{
    EDGE e;
    int i,res;
    sort(eg,eg+n,cmp);
    //        
    Init(m);

    //        
    res=0;
    for( i=0;i<n;++i )
    {
        e=eg[i];
        if( Find(e.u)!=Find(e.v) )
        {
            Combine(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main()
{
    int i,ans;
    bool bl;
    while( scanf("%d%d",&n,&m) && n )
    {
        for( i=0;i<n;++i )
            scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].cost);
        ans=Kruskal();
        
        //              
        bl=true;
        for(i=2;i<=m;++i)
            if( Find(1)!=Find(i) )
            {
                bl=false;
                break;
            }
            
        if( bl )    printf("%d
",ans);
        else    printf("?
");
    }
    return 0;
}

최소 생 성 트 리 를 만 드 는 Prim 알고리즘 을 만 들 었 습 니 다...
Prim 알고리즘 은 한 점 에서 전체 그림 으로 천천히 확장 하 는 것 입 니 다.
원리:
한 점 에서 출발 해서 이 점 과 직접 연 결 된 점 에서.가중치 가 가장 작은 쪽 을 찾 아 라.확장 을 진행 하 다.
근 데매번 찾 지 않 아 도 점 을 하나 더 늘 린 후,
이 집합 을 다른 각 점 의 거리 로 업데이트 하면 됩 니 다.
Prim 과 Kruskal 의 차이:
나의 이 해 는:
Prim 은 집합 전투 로 천천히 확장 되 고 하나씩 삼 키 며 마지막 으로 큰 나 무 를 구성한다.
한편,Kruskal 은 여러 개의 집합(≥1,하나의 집합 일 수도 있 음)으로 각각 작전 을 하고 마지막 에 하나의 큰 나무 로 합병한다.
Prim 과 Kruskal 의 우열:
Prim 은 매번 mincost 배열(각 점 에서 가장 짧 은 거리)을 유지 해 야 하기 때문에 O(n^2)가 필요 합 니 다.
그러나 가장 짧 은 길이 의 Dijkstra 와 마찬가지 로 더미 로 유지 하면 복잡 도 는 O(n log n)로 내 려 갈 수 있다.
Kruskal 알고리즘 은 정렬 에 가장 많은 시간 이 걸 릴 뿐 알고리즘 복잡 도 는 O(n log n)로 볼 수 있 습 니 다.
이 문제 의 Prim 알고리즘:

/****************************************
*****************************************
*        Author:Tree                    *
*From :http://blog.csdn.net/lttree      *
* Title :   project                     *
*Source: hdu 1863                       *
* Hint  :      （Prim   ）        *
*****************************************
****************************************/
#include <stdio.h>
#include <string.h>

#define RANGE 101
#define MAX 0x7fffffff
int cost[RANGE][RANGE];
int mincost[RANGE];
bool used[RANGE];

// n  。m  
int n,m;

int Min(int a,int b)
{
    return a<b?a:b;
}

void prim( void )
{
    // sum          
    int i,v,u,sum;
    //  1      ，   used  
    for( i=1;i<=n;++i )
    {
        used[i]=false;
        mincost[i]=cost[1][i];
    }
    sum=0;

    while( true )
    {
        v=-1;

        //          ，     
        for( u=1;u<=n;++u )
            if( !used[u] && (v==-1 || mincost[u]<mincost[v]) )
                v=u;

        if( v==-1 ) break;
        if( mincost[v]==MAX )   break;

        used[v]=true;
        sum+=mincost[v];

        //          
        for( u=1;u<=n;++u )
            mincost[u]=Min( mincost[u],cost[v][u] );
    }


    //             
    for( i=1;i<=n;++i )
    {
        if( used[i]==false )
        {
            printf("?
");
            return;
        }
    }
    printf("%d
",sum);
}

int main()
{
    int i,j;
    int u,v,c;

    while( scanf("%d%d",&m,&n) && m )
    {
        // init cost by MAX
        for( i=1;i<=n;++i )
            for( j=1;j<=i;++j )
            {
                if( i==j )  cost[i][j]=0;
                else    cost[i][j]=cost[j][i]=MAX;
            }
        for( i=0;i<m;++i )
        {
            scanf("%d%d%d",&u,&v,&c);
            cost[u][v]=cost[v][u]=c;
        }

        prim();
    }
    return 0;
}

저작권 성명:본 블 로그 의 오리지널 글,블 로그,동의 없 이 전재 할 수 없습니다.