首页 > 代码库 > 洛谷P2018 消息传递 树形DP
洛谷P2018 消息传递 树形DP
洛谷P2018 消息传递
树形DP
dp[ u ] 表示 u 节点 已经被传到,
然后将其字节点都传到所需要的最少时间
可知一个原则 一个树中的子树中如果同时开始传,那么最晚才能传到的,那他肯定最先开始传
因为本身需要的时间就大了,如果再晚一点开始,就要更晚才能结束了
也就是说从叶子向根传,将一个树中的子树 按照 他们直接传所需要的时间排序
优先传大的,再传小的
也就是一个点 只要负责好传到他们的儿子那些点就够了
1 #include <cstdio> 2 #include <cmath> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 #include <iomanip> 9 #include <vector> 10 using namespace std ; 11 12 const int maxn = 1011,inf = 1e9 ; 13 vector <int> f[maxn] ; 14 int n,mi,x,sum ; 15 int dp[maxn],ans[maxn] ; 16 17 inline void dfs(int u,int fa) 18 { 19 int cnt = 0,v ; 20 int tmp[maxn] ; 21 for(int i=0;i<f[ u ].size();i++) 22 { 23 v = f[ u ][ i ] ; 24 if(v!=fa) 25 { 26 dfs(v,u) ; 27 tmp[++cnt] = dp[ v ] ; 28 } 29 } 30 sort(tmp+1,tmp+cnt+1) ; 31 for(int i=1;i<=cnt;i++) 32 dp[ u ] = max(dp[ u ],tmp[ i ] + cnt -i+1) ; // 其中 cnt-i+1 表示的是 传给之前的儿子 33 //以及自身所需要的时间 34 } 35 36 int main() 37 { 38 scanf("%d",&n) ; 39 for(int i=2;i<=n;i++) 40 { 41 scanf("%d",&x) ; 42 f[x].push_back( i ) ; 43 f[i].push_back( x ) ; 44 } 45 mi = inf ; 46 for(int i=1;i<=n;i++) 47 { 48 for(int j=0;j<=n;j++) dp[ j ] = 0 ; 49 dfs( i,-1 ) ; 50 ans[ i ] = dp[ i ] ; 51 mi = min(mi,ans[ i ]) ; 52 } 53 printf("%d\n",mi+1) ; 54 55 56 for(int i=1;i<=n;i++) 57 if(ans[ i ]==mi) printf("%d ",i) ; 58 return 0 ; 59 }
洛谷P2018 消息传递 树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。