树形dpWA
查看原帖
树形dpWA
479066
MrJXS楼主2024/1/1 18:31
#include<bits/stdc++.h>
using namespace std;
struct line{
	int u,v,ap;
}l[205];
int n,q; 
int con[102][5],ls[102],rs[102],lc,apple[105],dp[105][105];
bool flag[102];
void buildtree(int root){
	if(!root) return;
	for(int i=1;i<=con[root][0];i++){
		if(flag[con[root][i]]) continue;
		if(ls[root]==0){
			ls[root]=con[root][i];
			flag[con[root][i]]=1;
		}else{
			rs[root]=con[root][i];
			flag[con[root][i]]=1;
		}
	} 
	buildtree(ls[root]);
	buildtree(rs[root]);
}
void putapple(int root){
	if(!root) return;
	for(int i=1;i<=2*n-2;i++){
		if(l[i].u==root&&l[i].v==ls[root]){
			apple[ls[root]]=l[i].ap;
		}
		else if(l[i].u==root&&l[i].v==rs[root]){
			apple[rs[root]]=l[i].ap;
		}
	}
	putapple(ls[root]);
	putapple(rs[root]);
}
void dfs(int u,int am){
	if(am==0) return;
	if(u==0) return;
	if(ls[u]==rs[u]){//叶子节点 
		dp[u][am]=apple[u];
		return;
	}
	int maxans=-1;
	for(int i=0;i<=am;i++){
		dfs(ls[u],i);
		dfs(rs[u],am-i);
		maxans=max(maxans,dp[ls[u]][i]+dp[rs[u]][am-i]);
	}
	dp[u][am]=maxans;
}
int main(){
	cin>>n>>q;
	for(int i=1,x,y,a;i<n;i++){
		cin>>x>>y>>a;
		l[++lc].u=x;
		l[lc].v=y;
		l[lc].ap=a;
		l[++lc].v=x;
		l[lc].u=y;
		l[lc].ap=a;
		con[x][++con[x][0]]=y;
		con[y][++con[y][0]]=x;
	}
	flag[1]=1;
	buildtree(1);
	putapple(1);
	dfs(1,q+1);
	cout<<dp[1][q+1]<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<=n;j++){
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	} 
	return 0;
}

帮忙看看出了什么问题,多谢

2024/1/1 18:31
加载中...