poj 2377 Bad Cowtractors 最大生成树

缘起

日常浪费生命 poj 2377 Bad Cowtractors

分析

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
Bessie要在John的N个谷仓之间修路（N个谷仓有M条路,路是有,只是未修, 要bessie来修），John要求用尽可能
少的路使得所有谷仓都能
联通，并且总距离最短，但是他又不想给Bessie钱。Bessie已经意识到John可能不给他钱，所
以他就想把这个工程做的最糟糕并且不让John发现。他决定用尽可能少的路使得所有谷仓都能
联通，但是要使总距离尽可能长。求这个可能的总距离。如果不能使得所有谷仓都联通，则输
出"-1"。

【输入】
N和M, 然后是M行，每行三个整数 A，B，C 表示A和B之间的双向道路修起来的话要花费C元
2 <= N <= 1,000
1 <= M <= 20,000
1 <= C <= 100,000

【输出】
最大生成树的花费

【样例输入】
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

【样例输出】
42

【限制】
1s

【hint】
OUTPUT DETAILS: 

The most expensive tree has cost 17 + 8 + 10 + 7 = 42. It uses the following 
connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.

这不就是最小生成树转一下变成最大生成树么? 稍微改一下prim的板子或者kruskal的板子就行了. 这里使用prim. 要是代码不懂的话，参考【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
75
76
77
78
79
80
81
//#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[1005],d[1005];
bool isInU[1005];
priority_queue<P,vector<P>, less<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[40005];

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, -1, sizeof(d));  // 伊始除了出发点之外,各个距离都是-1,因为是求最大生成树, 求的是最大值, 所以初始化为0, 这是和最小生成树第二个不同的地方
	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+=top.first;
			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));
			}
		}
	}
	for (int i = 1; i<=n; i++) // 说明尚有点未扩展进来（即原无向图不连通）, 说明办不到, 返回-1
	{
		if (!~d[i])
		{
			return -1;
		}
	}
	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 47ms
Memory 804kB
Length 1438
Lang C++
Submitted 2019-08-31 08:13:49
Shared
RemoteRunId 20820613

参考

【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/