Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

C++ Prim算法AC代码

Posted by 48694869 at 2019-08-03 17:04:00 on Problem 2485 and last updated at 2019-08-03 17:28:06
//题目要求:给出每两个村庄之间的距离矩阵,将所有村庄连接起来且总长度最短,输出连接村庄后最长的那条路
//也就是构建最小生成树求生成树里最长的一条边
#include <iostream>

using namespace std;

int n;             //村庄数
int G[505][505];   //邻接矩阵
int inTree[505];   //节点是否已经在生成树里
int distances[505];//节点到生成树最短距离

int Prim() {
	int maxLen = 0;
	inTree[1] = 1;                       //先把第一个节点加入生成树
	for (int i = 1; i <= n; i++) {
		distances[i] = G[1][i];      //更新最短距离数组
	}
	for (int k = 0; k < n - 1; k++) {  //要把剩下n-1个节点加入到生成树里
		int tempLen = 70000;  //随便找个比题目给出的距离最大值还大的数
		int tempIndex = -1;
		for (int m = 1; m <= n; m++) {
			if (!inTree[m] && distances[m] < tempLen) {  //找出不在生成树里的距离生成树最近的节点
				tempLen = distances[m];
				tempIndex = m;
			}
		}
		inTree[tempIndex] = 1;          //加入生成树
		if(maxLen < tempLen)            //用于更新生成树里最长的边
			maxLen = tempLen;
		for (int p = 1; p <= n; p++) {
			if (!inTree[p] && distances[p] > G[tempIndex][p])  //更新最短距离数组
				distances[p] = G[tempIndex][p];
		}
	}
	return maxLen;
}

int main()
{
	int cases = 0;
	cin >> cases;
	while (cases--) {
		cin >> n;
		memset(G, 0, sizeof(G));
		memset(inTree, 0, sizeof(inTree));
		memset(distances, 0, sizeof(distances));

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> G[i][j];
			}
		}

		int res = Prim();
		cout << res << endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator