poj 1258 Agri-Net 最小生成树

缘起

日常浪费生命 poj 1258 Agri-Net

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你N*N(3<=N<=100)矩阵，表示N个村庄之间的距离（<=100000）。FJ要把N个村庄全都连接起来，求连接的最短
距离。

【输入】
多样例. 对每个样例，第一行是N,然后是一个N*N矩阵

【输出】
对每个样例，输出最小代价

【样例输入】
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

【样例输出】
28

【限制】
1s

裸题的MST. 既可以prim，也可以kruskal. 但是考虑到本题是以邻接矩阵给出的图, 所以还是使用prim较好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef pair<int,int> P; // first是距离, second是顶点标号

int n,g[105][105], d[105];
bool isInU[105];

int prim()
{
	int ans = 0;
	priority_queue<P, vector<P>, greater<P> > pq; // 小根堆
	memset(d, 0x3f, sizeof(d));
	memset(isInU, 0, sizeof(isInU));
	d[1] = 0;
	isInU[1] = true;
	pq.push(P(0,1)); // 任意选取一个顶点进行MST的扩展,这里按照行规,选了1
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		if (!isInU[top.second]) // 这个判断不能少——只能拓展尚未加入的顶点
		{
			ans+=top.first;
			isInU[top.second] = true;
		}
		for (int i = 1; i<=n;i++)
		{
			if (i!=top.second&&d[i]>g[top.second][i]) // 拓展从top.second出发的边
			{
				d[i] = g[top.second][i];
				pq.push(P(g[top.second][i], i));
			}
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while (~scanf("%d", &n))
	{
		for (int i = 1;i<=n;i++)
		{
			for (int j  = 1; j<=n;j++)
			{
				scanf("%d", g[i]+j);
			}
		}
		printf("%d\n", prim());
	}
	return 0;
}

ac情况

Status Accepted
Memory 180kB
Length 1028
Lang C++
Submitted 2019-08-31 07:33:27
Shared
RemoteRunId 20820592

好啦~ 一块精美的堆优化过的prim板子出炉啦~