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

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

Problem Description

Input

Output

Example Input

3 21 2 11 3 11 0
Example Output
20
Hint
  
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;    }