[2018年第九届真题]采油最小生成树+贪心

410 阅读 6 评论 0 点赞

原题链接：蓝桥杯2018年第九届真题-采油

**第一问：** *最小生成树的模板，先求出一棵最小生成树，然后将这颗树的所有的权值乘上2。*
**第二问：** *可想最小的人数的情况，一定是留在生成树上的去维护每个点的人数之和，但是题目要求，如果这个点一旦建成就一定需要人去维护，那么这个最小的情况就会变成，如果在某个点上建立油井的人不足，这是因为能满足去维护的所有的人，但是这个点的油井建好了，这维护的人数一定要留下，到最后建油井的人会不足够，所以去寻找建立油井的人和维护油井的人之差最小。*

代码：
```
#include<bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pill;
const int N=100000+10;
int fa[N];
int a[N],b[N];
int n;
struct node{
	int u,v;
	int w;
}e[N];

inline int cmp(node s1,node s2)
{
	return s1.w>s2.w;
}

inline int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}

int main()
{
	ll sum=0,t=N;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=1;j<=n;j++)
	{
		scanf("%d",&b[j]);
		sum+=b[j];
		if(a[j]>b[j])
			t=min(t,(ll)(a[j]-b[j]));
		else
			t=min(t,(ll)0);	
	}
	sum+=t;
	
	int m=0;
	for(int i=2;i<=n;i++)
	{
		int u,w;
		scanf("%d%d",&u,&w);
		e[++m].u=i;
		e[m].v=u;
		e[m].w=w;
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	
	int cnt=0;
	ll ans=0;
	for(int i=1;i<n;i++)
	{
		int fat=find(e[i].v);
		int fbt=find(e[i].u);
		if(fat!=fbt)
		{
			ans+=e[i].w;
			fa[fbt]=fat;
			cnt++;
		}
		if(cnt==n-1) break;
	}
	printf("%lld %lld\n",ans*2,sum);
	return 0;
}
```

0.0分

1 人评分

本文分类：题解列表
浏览次数：410 次浏览
发布日期：2021-05-08 23:37:19
本文链接：https://blog.dotcpp.com/a/78952

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 6 条评论

已退役 2年前回复TA

@Klein @103517147 确实，已经是一个树了。你举得例子很对，这个解法有问题。

Klein 3年前回复TA

@Klein 而且n个点n-1条边   还是联通的 肯定就是一个树  不是图 不用求最小生成树 ，这题就是有病。

Klein 3年前回复TA

@Klein 有一个解答  最少人数就是维护人员之和  居然能过 说明输入数据肯定有问题。

Klein 3年前回复TA

@Klein 就是说如果2口＃ 一个10人建造2人维护   一个2人建造2人维护 那么按照你这个算法 维护人员之和加上最小差就是0，那么维护人员之和加上0即2+0+2=4<10肯定是不对的。

123456倍 3年前回复TA

@Klein 啊，这样写不对啊~~ 麻烦你可以写得再清楚一点吗？不太能理解你想表达的意思，QAQ

Klein 3年前回复TA

人员计算还是有问题把，当10 2  2 2   2+1+0=3   这不就不对了吗

[2018年第九届真题]采油 最小生成树+贪心

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 6 条评论

发表评论 取消回复

[2018年第九届真题]采油最小生成树+贪心

评论列表共有 6 条评论

发表评论取消回复