最小生成树（模板，注意和最短路的区别）

最小生成树模板。

#include <iostream>
#include<stdio.h>
#include<string.h>
#define MAX 0x3f3f3f3f
using namespace std;
int vis[1010];
int Map[1010][1010];
int dis[1010];
int n,m;
int prim()
{
    int i,j,now;
    int sum=0;
    for(i=1; i<=n; i++)
    {
        dis[i]=MAX;
        vis[i]=0;
    }
    for(i=1; i<=n; i++)
    {
        dis[i]=Map[1][i];
    }
    dis[1]=0;    //注意和最短路的区别，最短路的dis数组存的是从起点到该点的最短距离。而最小生成树存的是与该点相连的所有的边，最短的一条。
    vis[1]=1;
    for(i=1; i<n; i++)
    {
        now=MAX;
        int min1=MAX;
        for(j=1; j<=n; j++){
            if(!vis[j]&&dis[j]<min1){
                now=j;
                min1=dis[j];  //发现一条较短的边。
            }
        }
        if(now==MAX)
            break;
        vis[now]=1;
        //cout<<"now "<<now<<" min1 "<<min1<<endl;
        sum+=min1;  
        for(j=1; j<=n; j++)
        {
            if(vis[j]==0&&dis[j]>Map[now][j])
                dis[j]=Map[now][j];    //更新和now相连的所有的点的距离。
        }
    }
 cout<<sum<<endl;
}
int main()
{
    while((cin>>n)&&n){
        m=n*(n-1)/2;
        memset(Map,MAX,sizeof(Map));
        for(int i=0; i<m; i++){
            int a,b,c;
            cin>>a>>b>>c;
            if(c<Map[a][b])
                Map[a][b]=Map[b][a]=c;
        }
        prim();
    }
}