社区讨论

0分求助,我真的不知道为什么错了

P2015二叉苹果树参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1iheyj
此快照首次捕获于
2023/10/22 21:35
2 年前
此快照最后确认于
2023/11/02 22:30
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define ms(x,v) memset(x,v,sizeof(x));
using namespace std;
const int N = 105;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int f[N][N];//维度含义:1.当前节点i,2.砍k条边的最优解 
int n, q, head[N], cnt = 1;
struct Edge{
	int to, nxt;
}e[N*2];
int val[N], out[N], sz[N];
void addedge( int u , int v ){
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
void dfs( int u , int fa ){
	f[u][0] = val[u];
	if( out[u] == 0 ){
		sz[u] = 0;
		return ;
	}
	sz[u] = out[u];
	for( int i = head[u] ; i ; i = e[i].nxt ){
		int v = e[i].to;
		if( v != fa )dfs(v,u);
		for( int j = min(sz[u],q); j >= 0 ; --j ){
			for( int k = 0 ; k <= min(j,sz[v]) ; ++k ){
				f[u][j+k] = max(f[u][j+k],f[u][j-1]+f[v][k]);		
			}
		}
		if( v != fa )sz[u] += sz[v];
	}
}
int main()
{
	n = read(), q = read();
	int a, b;
	for( int i = 1 ; i < n ; ++i ){
		a = read(); b = read(); val[i] = read();
		addedge(a,b);
		addedge(b,a);
		out[a]++;
	}
	dfs(1,0);
	for( int i = 1 ; i <= n ; ++i )cout << sz[i] << " ";
	cout << f[1][q] << "\n";
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...