网站文字排版,重庆建设工程人力资源官网,手机之家报价大全2022,网站建设公司做前端P2018 消息传递 题目描述 巴蜀国的社会等级森严#xff0c;除了国王之外#xff0c;每个人均有且只有一个直接上级#xff0c;当然国王没有上级。如果A是B的上级#xff0c;B是C的上级#xff0c;那么A就是C的上级。绝对不会出现这样的关系#xff1a;A是B的上级#xf…P2018 消息传递 题目描述 巴蜀国的社会等级森严除了国王之外每个人均有且只有一个直接上级当然国王没有上级。如果A是B的上级B是C的上级那么A就是C的上级。绝对不会出现这样的关系A是B的上级B也是A的上级。 最开始的时刻是0你要做的就是用1单位的时间把一个消息告诉某一个人让他们自行散布消息。在任意一个时间单位中任何一个已经接到消息的人都可以把消息告诉他的一个直接上级或者直接下属。 现在你想知道 1.到底需要多长时间消息才能传遍整个巴蜀国的所有人 2.要使消息在传递过程中消耗的时间最短可供选择的人有那些 树形DP加入了记忆化设$dp[u][fa]$表示以$u$为儿子父亲为$fa$的传递的最大时间 状态转移方程为$dp[u][fa]max(dp[u][fa],it[i]cnt-i1)$ $it[i]$表示他的子树的大小$cnt$表示他子树的个数 贪心的走应该先走最大的子树所以走到第$i$小的子树的时间为$it[i]cnt-i1$即他子树的大小传递到他的时间1向下传递 #includecstdio
#includeiostream
#includecstdlib
#includevector
#includealgorithm#define inf 0x7fffffffusing namespace std;int n,dp[1005][1005],ans;
vectorintG[1005];int dfs(int u,int fa){if(dp[u][fa]) return dp[u][fa];int cnt0,it[1005],siG[u].size();for(int i0;isi;i){int vG[u][i];if(vfa) continue;it[cnt]dfs(v,u);}dp[u][fa]1;sort(it1,it1cnt);for(int i1;icnt;i)dp[u][fa]max(dp[u][fa],it[i]cnt-i1);return dp[u][fa];
}int main()
{scanf(%d,n);for(int u,i2;in;i){scanf(%d,u);G[u].push_back(i);G[i].push_back(u);}ansinf;for(int i1;in;i) ansmin(ans,dfs(i,0));printf(%d\n,ans);for(int i1;in;i) if(dp[i][0]ans) printf(%d ,i);return 0;
} 转载于:https://www.cnblogs.com/song-/p/9646527.html
