山东网站建设服务商,小程序制作,小广告模板,山东省建设教育集团网站首页题目传送门#xff1a;https://www.luogu.org/problemnew/show/P4438 题意#xff1a;
有n-1个点为城市#xff0c;n-1个点为农村#xff0c;每个城市连出两种道路#xff0c;一边为公路#xff0c;一边为铁路。现在每一个城市所连出的其中一种路都要修改#xff0c;求…题目传送门https://www.luogu.org/problemnew/show/P4438 题意
有n-1个点为城市n-1个点为农村每个城市连出两种道路一边为公路一边为铁路。现在每一个城市所连出的其中一种路都要修改求通过公式i表示第i个农村x 表示到城市1就是根的未被修复的公路y 表示到城市1就是根的未被修复的铁路所算出的最小值。 思路
树形dp。
考场竟然没有想出来太菜。
son[i][0]表示i的左儿子也就是修公路son[i][1]表示i的右儿子也就是修铁路。
f[i][j][k]表示第i个点到根经过j个未被修复的公路k个未被修复的铁路所得到的最小值。
最后用个记忆化搜索一下即可。 代码
#includecstdio
#includecstring
#includealgorithm
#define LL long long
using namespace std;int n;struct node{LL x,y,z;} a[20010];int son[20010][5];LL f[20010][45][45];
LL dfs(int x,int p,int q)
{if(xn) return a[x-n1].z*(a[x-n1].xp)*(a[x-n1].yq);if(f[x][p][q]!f[n1][41][41]) return f[x][p][q];return f[x][p][q]min(dfs(son[x][0],p,q)dfs(son[x][1],p,q1),dfs(son[x][1],p,q)dfs(son[x][0],p1,q));
}
int main()
{int x,y;scanf(%d,n);memset(f,63,sizeof(f));for(int i1;in;i){scanf(%d %d,x,y);if(x0) x-xn-1;if(y0) y-yn-1;son[i][0]x;son[i][1]y;}for(int i1;in;i)scanf(%lld %lld %lld,a[i].x,a[i].y,a[i].z);printf(%lld,dfs(1,0,0));
}
