小问题求助
查看原帖
小问题求助
810316
Qiluao楼主2023/8/4 16:56

状态转移时我没开tmp数组,采用的倒序遍历的方法,但是样例没过,输出0。感觉总体写的没问题,状态转移方程写的和正解是一样的,应该是边界或细节问题,求大佬指点!

void dfs(int root,int fa){
	f[root][1][1]=f[root][0][0]=0;//处理边界 
	for(int i=head[root];~i;i=ne[i]){
		if(ver[i]!=fa){
			dfs(ver[i],root);
			for(int j=k;j>=0;--j){
				for(int t=0;t<=j;++t){
					f[root][j][0]=min(f[root][j][0],f[root][j-t][0]+min(f[ver[i]][t][1],f[ver[i]][t][0]+(m==2)*w[i]));
					f[root][j][1]=min(f[root][j][1],f[root][j-t][1]+min(f[ver[i]][t][0],f[ver[i]][t][1]+w[i]));
				}
			}
		}
	}
}
2023/8/4 16:56
加载中...