데이터 구조의 도 론 - 최소 생 성 트 리 (prim + kruskal)

그림 구조 연습 - 최소 생 성 트 리
Time Limit: 1000MS Memory limit: 65536K
제목 설명
 n 개 도시 가 있 는데 그 중에서 일부 도시 간 에 도 로 를 건설 할 수 있 고 서로 다른 도 로 를 건설 하 는 비용 은 다르다.지금 우 리 는 최소한 얼마의 돈 을 써 서 도 로 를 건설 하면 모든 도 시 를 한데 연결 시 켜 임의의 도시 에서 출발 하여 다른 임의의 도시 에 도착 할 수 있 는 지 알 고 싶다.
 
입력
 여러 그룹 을 포함 하 는 데 이 터 를 입력 하 십시오. 형식 은 다음 과 같 습 니 다.
첫 번 째 줄 은 두 개의 정수 n m 를 포함 하고 도시 의 개수 와 건설 할 수 있 는 도로 의 개 수 를 대표 한다.(n<=100)
나머지 m 행 은 행 당 3 개의 정수 a b c 로 도시 a 와 도시 b 사 이 를 대표 하여 도 로 를 건설 할 수 있 고 대 가 는 c 이다.
 
출력
 각 조 의 출력 은 한 줄 을 차지 하고 출력 만 최소 화 합 니 다.
예제 입력

3 2

1 2 1

1 3 1

1 0

예제 출력

2

0

#include <iostream>

#include <string>

#include <stdio.h>

#include <string.h>

#define INF 99999999



using namespace std;

int sum;

int map[110][110];

int cost[110];

bool vis[110];



void prim(int n)   //             

{

    sum=0;

    int i, j, pos, mincost;



    memset(vis, false, sizeof(vis));

    for(i=1; i<=n; i++)

    {

        cost[i]=map[1][i];

    }

    vis[1]=true;

    for(i=1; i<n; i++)

    {

        mincost=INF;

        for(j=1; j<=n; j++)

        {

            if(!vis[j] && mincost>cost[j] )

            {

                mincost=cost[j];

                pos=j;

            }

        }

        vis[pos]=true;

        sum+=cost[pos];

        for(j=1; j<=n; j++)

        {

            if(!vis[j] && map[pos][j]<cost[j] )

            {

                cost[j]=map[pos][j];

            }

        }

    }

}



int main()

{

    int n, m;

    int i, j;

    int u, v, w;

    while(cin>>n>>m)

    {

        for(i=0; i<=n; i++)

        {

            for(j=0; j<=n; j++)

            {

                map[i][j]=INF;

            }

        }

        for(i=0; i<m; i++)

        {

            cin>>u>>v>>w;

            if(map[u][v] > w)

            {

                map[u][v]=w;

                map[v][u]=w;

            }

        }

        prim(n);

        cout<<sum<<endl;

    }

    return 0;

}