SDUT-2144 图结构练习——最小生成树

图结构练习——最小生成树

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic Discuss

Problem Description

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

Output

每组输出占一行，仅输出最小花费。

Example Input

Example Output

2
0

Hint

Author

#include<iostream>
#include <cstring>
#define Minimum  0x3f3f3f3f
using namespace std;
int Map[1010][1010];//用二维数组来表示图的边的关系
int visit[1010];//顶点标记数组，值为1表示访问过，为0则没有访问过
int lowcost[1010];//存储每个顶点与之相连边的权值
int n,m;
int prim()
{
    int i,j,k;
    int sum =0,flag=0;
    int Min;
    visit[1]=1;
    for(i=1;i<=n;i++)//权值初始化
    {
        lowcost[i]=Map[i][1];//邻接矩阵竖着建立
    }
    for(i=2;i<=n;i++)
    {
        Min  = Minimum;
        for(j=1;j<=n;j++)//寻找每个顶点与之相连的边的最小权值
        {
            if(!visit[j]&&lowcost[j]<Min)
            {
                Min = lowcost[j];
                k=j;
            }
        }
        sum+=Min;
        visit[k]=1;
        for(j=1;j<=n;j++)//从新更新权值
        {
            if(!visit[j]&&lowcost[j]>Map[j][k])
            lowcost[j]=Map[j][k];
        }
    }
        cout<<sum<<endl;
		return 0;
}
int main()
{
    int u,v,w;
    while(cin>>n>>m)
    {
        memset(Map,Minimum,sizeof(Map));
        memset(visit,0,sizeof(visit));
        if(m<n-1)//有n个点至少有n-1条路，如果少于说明不能完全联通
            cout<<0<<endl;
        else
        {
        while(m--)
        {
            cin>>u>>v>>w;
            if(Map[u][v]>w)//防止重复边的出现，保留权值小的
            Map[u][v]=Map[v][u]=w;
        }
        prim();
        }
    }
    return 0;
}

/***************************************************
User name: YT1658506207邵雪源
Result: Accepted
Take time: 44ms
Take Memory: 2160KB
Submit time: 2017-08-11 19:39:58
****************************************************/