poj2485 Prim算法

Prim算法

poj.org 2485.

#include "stdafx.h"
#include <iostream>
using namespace std;

#define MAX 1000
#define MAXCOST 0x3f3f3f3f

int graph[MAX][MAX];

int prim(int graph[][MAX], int n) //n顶点个数
{
	int lowcost[MAX]; //lowcost[i]:以i为终点的边的最小权值,lowcost[i]=0表示i点加入了MST
	int mst[MAX]; //mst[i]:对应lowcost[i]的起点,mst[i]=0表示起点i加入MST
	int i, j, min, minid;
	int max = 0;
	for (i = 2; i <= n; i++)
	{
		lowcost[i] = graph[1][i]; //从1开始到所有点的权值
		mst[i] = 1; //对应lowcost[i]的起点为1
	}
	mst[1] = 0; //1点在MST中
	for (i = 2; i <= n; i++)
	{
		min = MAXCOST; //min为最小权值
		minid = 0; //最小权值对应的点
		for (j = 2; j <= n; j++)
		{
			if (lowcost[j] < min && lowcost[j] != 0)
			{
				min = lowcost[j];
				minid = j;
			}
		}
		//输出示例V1-V3=1
		if (min > max)
			max = min; //最小权值累加
		lowcost[minid] = 0; //加入MST
		for (j = 2; j <= n; j++) //更新lowcost[]和mst[]
		{
			if (graph[minid][j] < lowcost[j] && lowcost[j] != 0)
			{
				lowcost[j] = graph[minid][j];
				mst[j] = minid;
			}
		}
	}
	return max;
}

int main()
{
	int T;
	int s;
	int sum;
	memset(graph, MAXCOST, sizeof(graph));
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &s);
		for (int i = 1; i < s + 1; i++)
			for (int j = 1; j < s + 1; j++)
			{
				scanf("%d", &graph[i][j]);
				if (!graph[i][j])
					graph[i][j] = MAXCOST;
			}
		sum = prim(graph, s);
		cout << sum << endl;
	}

	system("pause");
}