> #include <stdio.h>
> #include <iostream>
> #include <fstream>
> using namespace std;
> 
> int rode[1002][1002];
> int mark[1002];
> int que[1002];//将标记过的点加入到序列里面来
> int qnum;
> 
> int marknum;
> int totalcost;
> 
> int n,m;
> 
> bool prim(){
> 	if(marknum==n)return true;
> 	int max=0;
> 	int next=0; //下一个节点
> 	for(int i=0;i<qnum;i++){
> 		int curnode=que[i];
> 		for(int j=1;j<=n;j++){
> 			if(rode[curnode][j]!=0&&mark[j]==0){
> 				if(rode[curnode][j]>max){
> 					max=rode[curnode][j];
> 					next=j;
> 				}
> 			}
> 		}
> 	}
> 	if(max==0){
> 		return false;
> 	}else{
> 		totalcost+=max;
> 		marknum++;
> 		mark[next]=1;
> 		que[qnum++]=next;
> 		return prim();
> 	}
> 
> }
> 
> 
> void main(){
> //	ifstream cin("data.txt");
> //	cin>>n>>m;
> 	scanf("%d%d",&n,&m);
> 
> 	memset(rode,0,sizeof(rode));
> 	memset(mark,0,sizeof(mark));
> 	marknum=0;
> 	totalcost=0;
> 
> 	for(int i=0;i<m;i++){
> 		int f,e,cost;
> 		//cin>>f>>e>>cost;
> 		scanf("%d%d%d",&f,&e,&cost);
> 		rode[f][e]=cost;rode[e][f]=cost;
> 	}
> 
> 	mark[1]=1;
> 	marknum++;
> 	qnum=0;
> 	que[qnum++]=1;
> 
> 	if(prim()){
> 		printf("%d\n",totalcost);
> 		//cout<<totalcost<<endl;		
> 	}else{
> 		printf("-1\n");
> 	//	cout<<-1<<endl;
> 	}
> 	
> 
> }

• 500题了 留了念 (0) 20053565 2007-08-24 10:57:23