编辑代码

/*
实验三 贪心法及经典案例求解
实验内容
1.背包问题
2.最小生成数问题。
基本说明
任选一题，编写程序用贪心法求解此问题。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mmax 100
#define maxt 100000000
int v[mmax][mmax];
 
void Prim(int n){
	int low[mmax];
	int clo[mmax];
	bool s[mmax];
	s[1]=true;
	for(int i=2;i<=n;i++){
		low[i]=v[1][i];
		clo[i]=1;
		s[i]=false;
	}
	for(int i=1;i<n;i++){
		int min=maxt;
		int j=1;
		for(int k=2;k<=n;k++)
			if((low[k]<min)&&(!s[k])){
				min=low[k];
				j=k;
			}
			cout<<j<<" "<<clo[j]<<":"<<low[j]<<endl;
			s[j]=true;
			for(int k=2;k<=n;k++){
				if((v[j][k]<low[k])&&(!s[k])){
					low[k]=v[j][k];
					clo[k]=j;
				}
			}
	
	}
} 
 
int main()
{
	int n,m;
	cin>>n>>m;
	int ii,jj,tt;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)
		v[i][j]=maxt;
	}
	for(int i=0;i<m;i++){
		cin>>ii>>jj>>tt;
		v[ii][jj]=tt;
		v[jj][ii]=tt;
	}
	Prim(n);
	return 0;
}