123456倍

用户名：h1910819075

访问量：2473

签　名：

AC 总在意料之外

等　　级
排　　名	137
经　　验	7295
参赛次数	6
文章发表	6
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高-秘密行动题解
浏览：179

蓝桥杯2019年第十届真题-修改数组题解
浏览：152

题解 2302: 蓝桥杯2019年第十届真题-糖果
浏览：267

你可能喜欢

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

　　作者: 123456倍　　　　发表时间：2021-05-08 23:37:19 浏览：325　|　评论：1　

原题链接：蓝桥杯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分

4 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

Klein

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

2021-05-17 14:26:18

123456倍 2021-05-20 09:24:18 |

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

Klein 2021-05-22 14:34:06 |

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

Klein 2021-05-22 14:37:25 |

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

Klein 2021-05-22 14:41:31 |

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

已退役 2022-10-23 11:25:33 |

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

123456倍

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

母牛的故事（C语言代码）

K-进制数（C++代码）

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

评论区

精彩推荐

程序员的表白（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

输出九九乘法表（C语言代码）

1134题解(求分析)

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

盐水的故事（C语言代码）

小O的图案（C语言代码）

123456倍

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

母牛的故事 （C语言代码）

K-进制数 （C++代码）

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

评论区

精彩推荐

程序员的表白 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

输出九九乘法表 （C语言代码）

1134题解(求分析)

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

盐水的故事 （C语言代码）

小O的图案 （C语言代码）

母牛的故事（C语言代码）

K-进制数（C++代码）

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

　　评论区

程序员的表白（C语言代码）

输出九九乘法表（C语言代码）

盐水的故事（C语言代码）

小O的图案（C语言代码）