LuoguP1268树的重量【构造/思维】By cellur925
2024-08-26 23:25:13
Description
给你一个矩阵$M$,$M(i,j)$表示$i$到$j$的最短距离。定义树的重量为树上各边权之和,对于任意给出的合法矩阵$M$,已知它所能表示树的重量是唯一确定的。给出一个矩阵,求它所表示的树的重量。
Sol
这道题我想了一会发现什么思路都没有...然后企图画一点图也无济于事...
后来看题解发现我们其实可以从简单的角度入手,逐渐发现规律。
当有两个点的时候,显然答案就是$g(1,2)$。
当有三个点的时候,如图,发生了分叉。(因为各点都是叶子节点)
(图片引用自 @TsReaper)
设蓝线部分为$len$,那么树的重量就是$g(1,2)$+$len$。那么$len$部分怎么求?稍微想想可以得出$len=g(1,3)+g(2,3)-g(1,2)$再除以2。
类比一下,当有四个...五个...六个...点的时候,也会在某一个路径上发生分叉,而一个点只可能从在它编号之前的点分叉而来。于是我们对于每个点,枚举一下它是从它之前哪个点分叉过来的,取个最小值累加即可得到答案。
Code
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; int n,ans;
int f[][]; int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=;i<=n-;i++)
for(int j=i+;j<=n;j++)
scanf("%d",&f[i][j]),f[j][i]=f[i][j];
ans+=f[][];
for(int i=;i<=n;i++)
{
int tmp=0x3f3f3f3f;
for(int j=;j<=i-;j++)
tmp=min(tmp,(f[][i]-f[][j]+f[i][j])>>);
ans+=tmp;
}
printf("%d\n",ans);
ans=;
memset(f,,sizeof(f));
}
return ;
}
最新文章
- Spring(三)AOP面向切面编程
- c语言第8次作业
- [翻译]docker生态圈Mindmap
- 当findById(Integer id)变成String类型
- Hadoop学习笔记: 安装配置Hadoop
- highestAvailable比较灵活,毕竟大多数功能不需要系统最高权限(四种方法:屏蔽UAC,右键以管理员身份运行,增加manisfest,制作数字证书)
- 实现FileCopy(Ring0 x86 x64)
- powershell 生成随机用户信息
- 终于懂了:WM_PAINT 与 WM_ERASEBKGND(三种情况:用户操作,UpdateWindow,InvalidateRect产生的效果并不相同),并且用Delphi代码验证 good
- JSP 之国际化
- Python 随机生成有效手机号码及身份证
- 一个网卡配置多个ip配置实现,centos7系统
- JavaScript中的私有成员[翻译]
- Centos6.8实现SVN提交后自动更新目录
- 使用Fiddler进行手机端抓包
- tensorboard-sklearn数据-loss
- python之零碎知识
- “吃神么,买神么”的第一个Sprint计划(第二天)
- 微信小程序开发(五)开发框架MINA
- 整合最优雅SSM框架:SpringMVC + Spring + MyBatis 基础