TZOJ 5471: 数据结构实验--图的最小代价生成树

题目描述

求带权无向图的最小代价生成树。

 

输入

输入数据为多组，每组数据包含多行，第一行为2个整数n,e，n为图的顶点数，e为边数，接下来是e行，每行3个整数，前两个整数是一个顶点对，代表一条边所依附的两个顶点，第3个整数是边的权值。

所有值不超过20。

输出

请使用prim算法生成一棵生成树，并输出为生成树的各条边及其权值。格式见样例。

样例输入

5 7
1 2 1
1 3 1
2 3 4
2 4 2
2 5 1
3 4 5
4 5 6

样例输出

1 2 1
1 3 1
2 5 1
2 4 2

 

PS:太惭愧了，写了半天，输出的顺序就是不对，还是看了能人之后才发现自己错在哪里，明天附上代码（大佬如有更好见解或发现不对之处，欢迎评论，其为数据结构小白在线答题）

注释的话，最近满课，嗯，好忙啊555555

 

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define INF 0x3f3f3f;
int g[50][50],dis[50],vis[50],fa[50];

void prime(int n)
{
    int i,j,sum=0;
    memset(vis,0,sizeof(vis));
    for(i=1; i<=n; i++){
        dis[i]=g[1][i];fa[i]=1;
    }
       
    dis[1]=0;
    vis[1]=1;
    for(i=2; i<=n; i++)
    {
        int k=0,minn=INF;
        for(j=1; j<=n; j++)
            if(vis[j]==0)
               if(dis[j]<minn)
                  k=j,minn=dis[k];
       if(k==0) break;
       cout<<fa[k]<<" "<<k<<" "<<minn<<endl;
       vis[k]=1;
       //sum+=dis[k];
       for(j=1; j<=n; j++)
          if(vis[j]==0&&g[k][j]<dis[j]){
              dis[j]=g[k][j],fa[j]=k;
          }
    }//cout<<sum;
}

/*
两个写法都可以
void prime(int n)
{
    int i,j,sum=0;
    memset(vis,0,sizeof(vis));
    for(i=0; i<=n; i++){
        dis[i]=INF;
    }
       
    dis[1]=0;
    //vis[1]=1;
    for(i=1; i<=n; i++)
    {
        int k=0;
        for(j=1; j<=n; j++)
            if(vis[j]==0&&(k==0||dis[j]<dis[k]))
                  k=j;
       if(k==0) break;
       if(i!=1)
       cout<<fa[k]<<" "<<k<<" "<<dis[k]<<endl;
       vis[k]=1;
       //sum+=dis[k];
       for(j=1; j<=n; j++)
          if(vis[j]==0&&g[k][j]<dis[j]){
              dis[j]=g[k][j],fa[j]=k;
          }
    }//cout<<sum;
} 
*/
int main()
{
    int n,e,a,b,c,i,j;
    while(cin>>n>>e)
    {
        for(i=1; i<=n; i++)
          for(j=1; j<=n; j++)
             g[i][j]=INF;
        for(i=0; i<e; i++)
        {
            cin>>a>>b>>c;
            g[a][b]=g[b][a]=c;
        }
        prime(n);
    }
}