#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;
	}
	

}

• Re:有什么办法能不TLE么？ TLE了N次，每次都是超时15ms，郁闷呀！！ (12) 20053565 2007-08-24 10:40:04
• 用并查集 (1298) ecjtubaowp 2007-08-24 10:47:46
  • 500题了 留了念 (0) 20053565 2007-08-24 10:57:23
• acc了，原来是自己prim没搞明白，不好意思，丢人了！！：（ (0) zhb_msqx 2007-08-27 17:34:07