公路村村通30.zip

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

#include 
#include 
#include 

using namespace std;

/* run this program using the console pauser or add your own getch system（“pause“） or input loop */

#define MAX 100000
#define min（ a  b） （a）<（b）?（a）:（b）

int N=0M=0;

typedef struct Graph
{
	int matrix[1010][1010];
	bool visited[1010];
//	int vNum;
}* pGraph;

int cost[3010];
bool used[3010];

pGraph g;

void Creat（）
{
	g=（pGraph）malloc（sizeof（struct Graph））;
//	g->vNum=N;
	
	for（int i=0; i	{
		for（int j=0; j		{
			g->matrix[i][j]=MAX;
		}
		cost[i]=MAX;
		g->visited[i]=false;
	}
	for（int i=0; i	{
		int c1c2c;
		cin>>c1>>c2>>c;
		g->matrix[c1-1][c2-1]=g->matrix[c2-1][c1-1]=c;//
	}
}

void DFS（int v）
{
	if（g->visited[v]） return;
	g->visited[v]=true;
	for（int i=0; i	{
		if（!g->visited[i] && g->matrix[v][i] != MAX）
		{
			DFS（i）;
		}
	}
}


int Prim（）
{
	int res=0;
	for（int j=0; j	{
//		cost[j]=g->matrix[0][j];
		cost[j]=MAX;
		used[j]=false;
	}
	cost[0]=0;
	while（1）
	{
		int pos=-1;
		for（int i=0; i		{
			if（!used[i] && （pos==-1 || cost[i]			{
				pos=i;
			}
		}
		if（pos==-1） break;
		used[pos]=true;
		res+=cost[pos];
		for（int i=0; i		{
			cost[i]=min（cost[i]g->matrix[pos][i]）;
		}
	}
	return res;
//	for（int i=1; i//	{
//		for（j=1; j//		{
//			if（cost[j]!=0 && min>cost[j]）
//			{
//				min=cost[j];
//				pos=j;//找到最小的位置
//			}
//		}
//		if（pos == -1）//没有找到
//		{
//			break;
//		}
//		res+=cost[pos];
//		cost[pos]=0;
//		for（j=1; j//		{
//			if（cost[j] !=0 && g->matrix[pos][j]//			{
//				cost[j]=g->matrix[pos][j];
//			}
//		}
//	}
//	return res;
}
void printg（）
{
	for（int i=0; i	{
		for（int j=0; j		{
			cout<matrix[i][j]<<“ “;
		}
//		cout<visited[i];
		cout<	}
}

int main（int argc char** argv） {

	int ans;
	cin>>N>>M;
	Creat（）;
//	printg（）;
	
	DFS（0）;
	
	for（int i=0; i	{
		if（!g->visited[i]）
		{
			cout<<-1<			return 0;
		}
	}
	
	ans=Prim（）;
	cout<	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-06-18 20:24  06-图6. 公路村村通（30）\
     文件         936  2015-06-18 20:29  06-图6. 公路村村通（30）\06-图6. 公路村村通（30）.dev
     文件     1915305  2015-06-18 20:24  06-图6. 公路村村通（30）\06-图6. 公路村村通（30）.exe
     文件          97  2015-06-18 20:29  06-图6. 公路村村通（30）\06-图6. 公路村村通（30）.layout
     文件        2221  2015-06-18 20:24  06-图6. 公路村村通（30）\main.cpp
     文件       66004  2015-06-18 20:24  06-图6. 公路村村通（30）\main.o
     文件        1035  2015-06-18 20:24  06-图6. 公路村村通（30）\Makefile.win