圖結構練習——最小生成樹

2019-11-08 01:35:56

字體：大中小

來源：轉載

供稿：網友

HomeContestsPRoblemsRanklistStatus16120543046Logout

圖結構練習——最小生成樹

Time Limit: 1000MS Memory Limit: 65536KB SubmitStatistic

Problem Description

有n個城市，其中有些城市之間可以修建公路，修建不同的公路費用是不同的?，F在我們想知道，最少花多少錢修公路可以將所有的城市連在一起，使在任意一城市出發，可以到達其他任意的城市。

Input

輸入包含多組數據，格式如下。第一行包括兩個整數n m，代表城市個數和可以修建的公路個數。(n <= 100， m <=10000)剩下m行每行3個正整數a b c，代表城市a 和城市b之間可以修建一條公路，代價為c。

Output

每組輸出占一行，僅輸出最小花費。

Example Input

3 21 2 11 3 11 0Example Output
20Hint
  Author
 趙利強 一道模版題。。用kruskal硬生生地怼了一個下午。。。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define INF 999999using namespace std;int n,m;int map[1005][1005];int vis[1005];int dist[1005];int prime(){    int sum=0;    int i,j;    memset(vis,0,sizeof(vis));    vis[1]=1;    int t;    for(i=1; i<=n; i++)    {        dist[i]=map[1][i];    }    for(i=1; i<=n; i++)    {        int min=INF;        for(j=1; j<=n; j++)        {            if(!vis[j]&&dist[j]<min)            {                min=dist[j];                t=j;            }        }        if(min==INF) break;        vis[t]=1;        sum+=min;        for(j=1; j<=n; j++)        {            if(!vis[j]&&dist[j]>map[t][j])                dist[j]=map[t][j];        }    }    return sum;}int main(){    while(~scanf("%d%d",&n,&m))    {        int i;        memset(map,INF,sizeof(map));        //memset(dist,INF,sizeof(dist));        for(i=1;i<=m;i++)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            if(map[u][v]>w)            {                map[u][v]=w;                map[v][u]=w;            }        }        int sum=prime();        printf("%d/n",sum);    }    return 0;}/***************************************************User name: Result: AcceptedTake time: 16msTake Memory: 2060KBSubmit time: ****************************************************/這個是模版↓//模板int prime(int cur){    int index;    int sum = 0;    memset(visit, false, sizeof(visit));    visit[cur] = true;    for(int i = 0; i < m; i ++){        dist[i] = graph[cur][i];        }        for(int i = 1; i < m; i ++){                int mincost = INF;        for(int j = 0; j < m; j ++){            if(!visit[j] && dist[j] < mincost){                mincost = dist[j];                index = j;                }            }                visit[index] = true;        sum += mincost;                for(int j = 0; j < m; j ++){            if(!visit[j] && dist[j] > graph[index][j]){                dist[j] = graph[index][j];            }            }        }     return sum;    }