[SDUT] (3362) 데이터 구조 실험의 도 론 6: 마을 통 도로 - 최소 생 성 나무 (그림)

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

Example Output

19

주: 가중 무방 향도
새로운 지식 배우 기:
       ① 나무 (tree) 는 고리 가 없 는 그림 이다.나무의 특수 한 그림 이 라 고 할 수 있 습 니 다. 나무 에서 임의의 정점 r 와 정점 v 는 반드시 하나의 경로 가 존재 합 니 다.정점 에 n 개가 있 으 면 최소 생 성 나무의 가장자리 에 n - 1 개가 있 습 니 다.최소 생 성 트 리 (Minimum Spanning Tree) 는 각 변 의 가중치 가 가장 작은 생 성 트 리, 즉 최소 생 성 트 리 는 그림 의 하위 그림 을 말한다.
       ②: 프 림 알고리즘 (Prim 's Algorithm) 은 최소 생 성 트 리 (MST) 를 구 하 는 대표 적 인 알고리즘 중 하나 입 니 다.
       ③: 학습 을 통 해 Prim 알고리즘 (최소 생 성 트 리) 과 dijkstra 알고리즘 (최 단 경로) 이 서로 다른 점 을 깊이 느 꼈 습 니 다!
 
참고 자료:
최소 생 성 트 리 Prim 알고리즘 이해:http://blog.csdn.net/yeruby/article/details/38615045
 
AC 코드:

#include
#include
#define INF 0x3f3f3f3f
#define MAX 1005
using namespace std;
int mmap[MAX][MAX];
bool vis[MAX];
int dist[MAX];
int prim(int n) //             (MST)
{
    for(int i=1;i<=n;i++)
        dist[i]=mmap[1][i];
    vis[1]=true;
    int k;
    int mmin;
    int sum=0;
    for(int i=1;i>n>>m)
    {
        int u,v,w;
        memset(mmap,0,sizeof(mmap));
        memset(vis,false,sizeof(vis));
        memset(dist,0,sizeof(dist));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    mmap[i][j]=0;
                else
                    mmap[i][j]=INF;
            }
        }
        while(m--)
        {
            cin>>u>>v>>w;
            if(w