这一题我试着将ans初始化为负无穷,或者w1(第一个权值),因为怕所有权值都是负数,但是另ans=0反而满分,而另ans为负无穷却只有79%的分值。大家知道怎么回事吗?
解题思路:
其实就是无根树转化为有跟树,并且在遍历的时候加入一些判断条件就行
注意事项:
注意要将ans定义为long long型
参考代码:
#include<iostream> #include<bits/stdc++.h> using namespace std; const int MAXN=1e5; long long w[MAXN+1];//每个点权重 long long v[MAXN+1];//每个点作为根节点时得到的最大圈和 //int ans=0xc0c0c0c0; long long ans; vector<int> g[MAXN+1];//邻接表 using namespace std; //以root为根,算出最大的权和 void dfs(int root,int fa){ v[root]=w[root]; for(int i=0;i<g[root].size();++i){ int son=g[root][i];//期中一个孩子 if(son!=fa){ dfs(son,root); if(v[son]>0){ v[root]+=v[son]; } } } if(v[root]>ans){ ans=v[root]; } } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; } ans=w[1]; for(int j=1;j<=n-1;j++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } ans=w[1]; dfs(1,0); cout<<ans<<endl; return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:1066 |
C语言训练-计算:t=1-1/(2*2)-1/(3*3)-...-1/(m*m) (C语言代码)浏览:780 |
矩阵乘法 (C++代码)浏览:1454 |
多输入输出练习1 (C语言代码)浏览:1177 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:377 |
C语言训练-大、小写问题 (C语言代码)浏览:611 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:901 |
1908题解浏览:633 |
核桃的数量 (C语言代码)浏览:668 |
1128题解(返回值为数组的情况)浏览:450 |