123456倍

**第一问：** *最小生成树的模板，先求出一棵最小生成树，然后将这颗树的所有的权值乘上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 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

Klein

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

2021-05-17 14:26:18

123456倍

TA的其他文章

你可能喜欢

人民币问题（C语言代码）

简单的a+b （C语言代码）

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

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

wu-理财计划（C++代码）

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

评论区

精彩推荐

C语言训练-亲密数（C语言代码）

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

字符逆序（C语言代码）

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

简单的a+b （C语言代码）

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

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

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

A+B for Input-Output Practice (I) （C语言代码）

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

123456倍

TA的其他文章

你可能喜欢

人民币问题 （C语言代码）

简单的a+b （C语言代码）

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

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

wu-理财计划 （C++代码）

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

评论区

精彩推荐

C语言训练-亲密数 （C语言代码）

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

字符逆序 （C语言代码）

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

简单的a+b （C语言代码）

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

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

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

A+B for Input-Output Practice (I) （C语言代码）

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

人民币问题（C语言代码）

wu-理财计划（C++代码）

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

　　评论区

C语言训练-亲密数（C语言代码）

字符逆序（C语言代码）

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