1、题目的意思为找到一颗树中,删除该树中的某一个节点后,其所剩的子树的最大结点数最少
2、要找到该结点,首先我们要先算出所有树每个节点,以该节点为跟的子树的总结点数,设为tot[i], 那么设f[i]为删除i节点后,所剩子树的最大结点数,则f[i] = max(n-tot[i], tot[k]);k为以i为跟的子树。
3、求tot[i],首先明确tot[i] = 1+总tot[k](指i为根节点的所有子树), 我们可以利用dfs,找到根节点后,从根节点开始搜,先初始化tot[i] = 1,然后遍历其子树,加上其总结点数即可
4、答案即为所有f[i]中的最小值
- # include
- using namespace std;
- int n, root, ans = 1010, rans = 0;
- int tot[1010];
- int f[1010];
- vector<int> ve[1010];
- void dfs(int r)
- {
- tot[r] = 1;
- int maxn = 0;
- for (int i=0; i
size(); i++) - {
- int j = ve[r][i];
- dfs(j);
- tot[r] += tot[j];
- }
- }
- int main()
- {
- cin>>n;
- root = (1+n)*n/2;
- for (int i=1; i
- {
- int x, y;
- cin>>x>>y;
- ve[x].push_back(y);
- root-=y;
- }
- dfs(root);
- for (int i=1; i<=n; i++)
- {
- int maxx = 0;
- for (int j=0; j
size(); j++) - maxx = max(maxx, tot[ve[i][j]]);
- f[i] = max(maxx, n-tot[i]);
- if (f[i]
- {
- ans = f[i];
- rans = i;
- }
- }
- cout<
" "< -
- return 0;
- }
NC51178 没有上司的舞会
题目链接
关键点:
1、首先明确,对于每一个开心值,只有当其父节点不选时,其子节点才存在开心值(即上司不在),那么该题就是求不连通的树的,能取到开心值的最大值
2、对于每一个人的去或者不去,我们可以用0、1来表示,那么f[i][0],表示i不参加所能取到的最大开心值,f[i][1]表示i参加所能取到的最大开心值,
f[i][0] += max(f[j][1], f[j][0]);j表示i的孩子,对于i不参加,那么其孩子可以选择参加或者不参加
f[i][1] += f[j][0];对于i参加,那么j就一定不参加
3、初始化,对于f[i][0]表示i不参加,初始化值为0,对于f[i][1]参加,初始化值为i的开心值
4、我们搜索从跟开始搜索,答案即为根选或者不选
完整代码:
- # include
- using namespace std;
- int n, root;
- int h[6010];
- vector<int> ve[6010];
- int f[6010][2];
- void dfs(int r)
- {
- f[r][0] = 0;
- f[r][1] = h[r];
- for (int i=0; i
size(); i++) - {
- int j = ve[r][i];
- dfs(j);
- f[r][0] += max(f[j][0], f[j][1]);
- f[r][1] += f[j][0];
- }
- }
- int main()
- {
- cin>>n;
- root = (n+1)*n/2;
- // cout<
- for (int i=1; i<=n; i++)
- {
- cin>>h[i];
- }
- int x, y;
- cin>>x>>y;
- while (x&&y)
- {
- root-=x;
- ve[y].push_back(x);
- cin>>x>>y;
- }
- // cout<
- dfs(root);
- cout<<max(f[root][0], f[root][1]);
- return 0;
- }
-
相关阅读:
批处理小程序的制作
u盘上面 安装 ubuntu 系统
牛客练习赛106 E(二分图捏)
深度学习文本预处理利器:Tokenizer详解
如何快速实现一个可视化看板?
SpringBoot集成WebSocket实现在线聊天
linux篇---修改图片权限
PX4模块设计之二十八:RCInput模块
代码随想录算法训练营 动态规划part16
JVM调优工具锦囊:JDK自带工具与Arthas线上分析工具对比
-
原文地址:https://blog.csdn.net/m0_60531106/article/details/126843389
-
最新文章
-
C++11 线程同步接口std::condition_variable和std::future的简单使用
Go runtime 调度器精讲(十一):总览全局
Spring框架漏洞总结
Angular 18+ 高级教程 – 国际化 Internationalization i18n
基于Tauri2+Vue3搭建桌面端程序|tauri2+vite5多窗口|消息提醒|托盘闪烁
ComfyUI 基础教程(五) —— 应用 IP-Adapter 实现图像风格迁移
网络空间的“边水往事”?针对华语黑产及用户进行攻击的 APT-K-UN3 活动分析
伪装“黑神话悟空修改器”传播木马的活动分析
全球蓝屏后,微软决定将安全踢出Windows内核
Java读取寄存器数据的方法