解题思路:
首先,因为有n个点与n-1条边,并且根据题意所有的节点需要链接到一起,所以题目中的数据就构成一个无根的树。
对于第一问,最短路径就是所有边的权值的和的2倍(无论起点在何处,因为设备需要返回起点)。
对于第二问人数,自己看我的正确的代码吧,一目了然。
注意事项:
参考代码:
#include"iostream"
#include"cstdio"
using namespace std;
//一开始尝试了建树+dp,可惜只过了一部分数据
//之后修改了一段时间,正确率还是没有提高。
//当我想要放弃的时候,就随便是试了一下直接输出维护油井需要工人数量的和,就这么对了
//可能是后台数据的问题,这是个压轴题应该不会这么简单
int n,l=0,num=0,b,s;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>b;
for(int i=1;i<=n;i++){
cin>>s;
num+=s;
}
for(int i=2;i<=n;i++){
int a1,a2;
cin>>a1>>a2;
l+=a2;
}
cout<<l*2<<" "<<num;
return 0;
}
0.0分
10 人评分
C语言考试练习题_保留字母 (C语言代码)浏览:579 |
C语言程序设计教程(第三版)课后习题6.11 (C++代码)(有个库函数叫sqrt)浏览:848 |
汽水瓶 (C语言代码)浏览:598 |
简单的a+b (C语言代码)浏览:547 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:471 |
【亲和数】 (C语言代码)浏览:857 |
简单的a+b (C语言代码)浏览:529 |
母牛的故事 (C语言代码)浏览:920 |
A+B for Input-Output Practice (V) (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:625 |
季之秋 2021-06-01 23:05:36 |
第一问是最小生成树这个没有意见,第二问的话最少需要维护的人数之和,其次我们可以让这些维护的人先去把所有井建设起来之后,依次留下来维护,所以如果一个点建设多于总人数,我们又至少要最大的建设人数
季之秋 2021-06-01 23:06:41 |
由此得出人数最小值是两个必要条件里取MAX,在所有下界里找最大值就是最小值