题解 P1122 【最大子树和】
首先,这个题,我看过大家的题解之后感触很深.在这里,我提出的是一种优化的 BFS .
问题描述:
看题目就可以看出来,是一个最大子树和,我的第一反应是用DP和DFS 做,搜索他所有的子树,如果大于零就选,小于零就扔了.
后面我会附上代码.这里记忆化DFS的代码,还请大家多多指点.
关于我的BFS
- 做完之后我看了一下题解,发现楼下的dalao写可以用BFS做,于是我就开始尝试使用BFS做这个.但是A掉之后看了一下并不相同,所以我打算发这篇题解.
基本思路:
-
使用记忆路径的BFS进行搜索,并使用数组来存储结果(为了下一步返回来用),最后从叶子节点向上更新就好了.
-
如果自己的结果大于零,就把它叠加到父亲里面,如果小于零则不更新.
-
在每一次处理之后,直接更新答案,免除最后O(n)的查询.
-
最后建出图来就当于是从下向上的DP,只不过是另一种形式罢了
处理方法:
-
使用邻接表存图.
-
使用常规记录路径的BFS搜索,记录父节点,方便更新.
-
在搜索到子节点的时候更新父节点,这样就可以处理一个节点多个孩子还要再搜一遍的时间.
STL优化:
-
可以用stack与queue来实现,这两个容器在O2下应该更快一些吧.
-
vector这个东西可以给你的记录省空间.
我的BFS 代码:
#include<bits/stdc++.h>
using namespace std;
//以下建图
int n,fir[16010],bea[16010],fr,tos,taile;
struct list{
int to,next;
}s[32010];
void add(int x,int y){
s[++taile].to=y;
s[taile].next=fir[x];
fir[x]=taile;
s[++taile].to=x;
s[taile].next=fir[y];
fir[y]=taile;
}
//以下搜索
bool vis[16010];int tail=1,head,point,sil;
int bfsx[16010],fao[16010],ans[16010];
void bfs(int x){
while(head<tail){ //一般的BFS
head++;
point=bfsx[head],sil=fir[point];
while(sil!=0){
if(!vis[s[sil].to]){ //记录路径
bfsx[++tail]=s[sil].to;
fao[s[sil].to]=point;
vis[s[sil].to]=1;
}
sil=s[sil].next;
}
}
for(int i=n;i>=1;i--){ //更新结果.使用的是上面储存下来的BFS序的反序(上面提到了可以用queue弹出直接接到stack里面)
ans[bfsx[i]]+=bea[bfsx[i]]; //处理到自己再把自己加上,免得在子树处理的时候由于加自己加多加少的问题出现的错误
if(ans[bfsx[i]]>=0 && i!=1)ans[fao[bfsx[i]]]+=ans[bfsx[i]]; //更新父节点,如果答案大于零,更新.至于那个i!=0是因为我使用ans[0]储存的结果,ans[0]肯定不能被更新啊
ans[0]=max(ans[0],ans[bfsx[i]]); //直接记录结果
}
}
//以下主函数
int main(){ //这个我就不解释了
cin>>n;
for(int i=1;i<=n;i++)cin>>bea[i];
for(int i=1;i<n;i++){
cin>>fr>>tos;
add(fr,tos);
}
bfsx[tail]=1;vis[1]=1;
bfs(1);
cout<<ans[0];
return 0;
}emm.........
这边水一下我的DFS 希望dalao们看到了有什么优化私信发我一下,谢谢谢谢.这个我就不写注释了,楼下的dalao们讲的比我好得多!!!
#include<bits/stdc++.h>
using namespace std;
//以下建图
int n,fir[16010],bea[16010],fr,tos,taile;
struct list{
int to,next;
}s[32010];
void add(int x,int y){
s[++taile].to=y;
s[taile].next=fir[x];
fir[x]=taile;
s[++taile].to=x;
s[taile].next=fir[y];
fir[y]=taile;
}
//以下搜索
bool vis[16010];
int ans[16010],point,ansn;
int dfs(int x){
if(ans[x]) return ans[x];
ans[x]=bea[x];
vis[x]=1;int lis=fir[x];
while(lis!=0){
if(!vis[s[lis].to]){
ansn=dfs(s[lis].to);
if(ansn>=0) ans[x]+=ansn;
ans[0]=max(ans[x],ans[0]);
}
lis=s[lis].next;
}
vis[x]=0;
return ans[x];
}
//以下主函数
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>bea[i];
for(int i=1;i<n;i++){
cin>>fr>>tos;
add(fr,tos);
}
dfs(1);
cout<<ans[0];
return 0;
}