데이터 구조 - 최소 생 성 트 리 (C 언어)

데이터 구조 실험의 도 론 9: 최소 생 성 트 리
Problem Description n 개 도시 가 있 는데 그 중에서 일부 도시 간 에 도 로 를 건설 할 수 있 고 서로 다른 도 로 를 건설 하 는 비용 은 다르다.지금 우 리 는 최소한 얼마의 돈 을 써 서 도 로 를 건설 하면 모든 도 시 를 한데 연결 시 켜 임의의 도시 에서 출발 하여 다른 임의의 도시 에 도착 할 수 있 는 지 알 고 싶다.
Input 입력 은 여러 그룹의 데 이 터 를 포함 하고 형식 은 다음 과 같 습 니 다.
첫 번 째 줄 은 두 개의 정수 n m 를 포함 하고 도시 의 개수 와 건설 할 수 있 는 도로 의 개 수 를 대표 한다.(n <= 100， m <=10000)
나머지 m 행 은 행 당 3 개의 정수 a b c 로 도시 a 와 도시 b 사 이 를 대표 하여 도 로 를 건설 할 수 있 고 대 가 는 c 이다.
출력 은 각 그룹의 출력 이 한 줄 을 차지 하고 출력 만 최소 화 합 니 다.
Sample Input 3 2 1 2 1 1 3 1 1 0
Sample Output 2 0

#include
#include
#define INF 0x3f3f3f3f  //     
#define N 1010

int vis[N];  //    ；
int mp[N][N];  //        ；
int dist[N];  //                        ；
int n,m;

int prim()  //     
{
    int sum=0;
    int i,j;
    vis[1]=1;  //         1；                ；
    for(i=1; i<=n; i++)
    {
        dist[i]=mp[1][i];//                    dist   ；
    }
    for(i=1; i<n; i++)//      n-1          ，    n-1   ；
    {
        int min=INF;
        int p=-1;
        for(j=1; j<=n; j++) //      dist  ，                ；
        {
            if(vis[j]==0&&min>dist[j])
            {
                min=dist[j];
                p=j;
            }
        }
        if(min == INF) //         ，       ；
        {
            return -1;
        }
        sum=sum+min; //       sum 
        vis[p]=1;	//            ，        1；
        for(j=1; j<=n; j++)//                         ，   dist    ；
        {
            if(vis[j]==0&&dist[j]>mp[p][j])
            {
                dist[j]=mp[p][j];
            }
        }
    }
    return sum;
}

int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++)
            {
                mp[i][j]=INF;
            }
        }
        for(i=1; i<=m; i++)
        {
            int a;
            int b;
            int c;
            scanf("%d %d %d",&a,&b,&c);
            mp[a][b]=c;
            mp[b][a]=c;
        }
        int k=prim();
        printf("%d
",k);
    }
    return 0;
}