p1268树的重量 题解
2024-09-05 10:04:54
题面描述点此qwq。
正解开始。
一道茅塞顿开恍然大悟的题目:
第一眼看到这个题的时候,语文不好的我对着题目中的
这些,和:
这句话发呆半天,,,,
因为不关我怎么构建几何模型,我都不理解这句话。。
(吐槽题面臃肿!)
然后想了一下,发现题目是这个亚子:
给你一个矩阵M,M上每一个节点(i,j)表示叶子结点i和叶子结点j的距离,每个矩阵有且只能生成唯一一个树(不然这题没法搞了),让你求这棵树上的每一条边的权值和。
在李姐(lz dalao)完题目之后,我又开始懵了。。。。。。到底怎么搞非叶节点的位置???暴力恐怕不行的。。
百思不得其解后,我在绝望中从最简单情况递推:
考虑只有两个(n=2)节点1,2,一条边权值为3
这种情况:
那么,两个节点自然权值就为3了,答案也是3。
一旦跨越到n=3这种情况,就有些棘手。
因为3个节点都是叶子结点,那么必然要在1到2的路径上选一个中间节点来连接3号节点。
(选哪里好呢..?)
因为1到3和2到3的长度都知道了,那么我们可以利用数学方法求助3的位置。
假设M[1][3]=4,M[2][3]=3,那么这两条路径必然有和1到2的路径重复的。
那么我们减去重复的,就是3节点到1,2路径的距离了。
如图:
公式:(jz[1][3]+jz[2][3]-jz[1][2])/2=(4+3-3)/2=2.
那么,理解了这个以后,我们可以顺着推n>3的情况:
从之前n-1的情况中找两个点之间的路径,并尝试插入当前节点,然后取min。
节点太多就不画了。。
上代码吧。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; inline int read()
{
int ans=;
char ch=getchar(),last=' ';
while(ch<''||ch>'')last=ch,ch=getchar();
while(ch>=''&&ch<='')ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
return last=='-'?-ans:ans;
} int n,jz[][]; int main(){
n=read();
while(n!=)
{
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
jz[j][i]=read(),jz[i][j]=jz[j][i];
int ans=jz[][];
for(int i=;i<=n;i++)
{
int dt=0x3f3f3f3f;
for(int j=;j<=i-;++j)
for(int k=;k<=j-;++k)
{
dt=min(dt,(jz[j][i]+jz[k][i]-jz[j][k])>>);
}
ans+=dt;
}
printf("%d\n",ans);
n=read();
}
}
完结。
最新文章
- android 史上最简单易懂的跨进程通讯(Messenger)!
- 编译安装mysql(Ubuntu10 64位)
- PLSQL_Oracle Lock锁的处理(案例)
- SQl 字段中出现某一个词语的次数
- C#编程使用Managed Wifi API连接无线SSID
- RhinoMocks简单范例
- [MongoDB] Introduce to MongoDB
- cocos2dx进阶学习之屏幕适配
- ZOJ 3635 Cinema in Akiba(线段树)
- Ubuntu下安装vmware 9.0 + 注册码
- 计时器 Timer
- margin叠加相邻两个元素的上下margin是叠加在一起
- hdu_1012(水题。。。不能再水)
- 【Python】 virtualenv虚拟环境建设和管理
- Jmeter(GUI模式)教程
- Wannafly挑战赛23B游戏
- 团队项目个人进展——Day10
- Docker命令之 build
- Sailing
- VS2013的IDE开发使用便捷实用技巧----(补充)
热门文章
- 云计算openstack核心组件--glance-镜像服务(6)
- C学习笔记-第一个C语言程序
- PYTHON 100days学习笔记002:语言元素-数字变量与运算符
- [转帖] ./demoCA/newcerts: No such file or directory openssl 生成证书时问题的解决.
- redis 持久化之 RDB &; AOF
- C++中的bool类型
- Selenium IDE for firefox
- go intall的使用
- poj 2226 Muddy Fields (二分图)
- nnginx配置代理服务器