poj 2395 Out of Hay 最小生成树

缘起

日常浪费生命 poj 2395 Out of Hay

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
有N（2-2000）个农场，M（1-10000）条双向通路连通各个农场，长度不超10^9，要求遍历全部的农场，且每走1单
位长度就要消耗一单位水，每到一个农场可以把自己的水充满，求最小的水箱容量。

【输入】
N和M, 然后M行分别是三个数 A，B， C表示A和B之间的通路长C

【输出】
水箱最少水量

【样例输入】
3 3
1 2 23
2 3 1000
1 3 43

【样例输出】
43

【限制】
1s

裸体prim(只需要把求cost的过程中的求和改成求max即可)，不解释. 参见【1】

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
62
63
64
65
66
67
68
69
70
71
72
73
74
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef pair<int,int> P;

int n,m,cnt,head[2005],d[2005];
bool isInU[2005];
priority_queue<P,vector<P>, greater<P> > pq;
struct Arc
{
	int from,to,nxt,len;
	Arc(){}
	Arc(int from,int to,int nxt,int len):from(from), to(to),nxt(nxt), len(len){}
}g[20005];

void addArc(int a, int b, int c)
{
	g[cnt] = Arc(a,b,head[a],c);
	head[a] = cnt++;
	g[cnt] = Arc(b,a,head[b],c);
	head[b] = cnt++;
}

int prim()
{
	int ans = 0;
	memset(d, 0x3f, sizeof(d));
	d[1] = 0;
	isInU[1] = true;
	pq.push(P(0,1));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		if (!isInU[top.second])
		{
			ans = max(top.first,ans); // 和传统的prim相比, 就是这里不一样——传统的prim是求和, 这里是求max
			isInU[top.second] = true;
		}
		for (int h = head[top.second]; ~h; h = g[h].nxt)
		{
			int to = g[h].to;
			if (d[to]>g[h].len)
			{
				d[to] = g[h].len;
				pq.push(P(d[to], to));
			}
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		addArc(a,b,c);
	}
	printf("%d\n", prim());
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 500kB
Length 1284
Lang C++
Submitted 2019-08-31 08:43:39
Shared
RemoteRunId 20820658

参考

【1】https://yfsyfs.github.io/2019/08/30/poj-1258-Agri-Net-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/