[Luogu] P1131 [ZJOI2007]时态同步
题目描述
题目描述
小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成,我们不妨称之为节点,并将其用数字1,2,3…进行标号。电路板的各个节点由若干不相交的导线相连接,且对于电路板的任何两个节点,都存在且仅存在一条通路(通路指连接两个元件的导线序列)。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后,产生一个激励电流,通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后,得到信息,并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终,激励电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的,对于每条边e,激励电流通过它需要的时间为te,而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求,故需要通过改变连接线的构造。目前小Q有一个道具,使用一次该道具,可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步?
题目解析
树形DP吗?完全不会不知道为什么要用。
贪心就可以了
首先明确一个性质:
要使得所有叶子的深度相同,那么对于任意一个点,每个子树的深度都必须相同。
证明:
可以用反证法,如果有一个节点x,它的子树的深度各不相同,那这些子树的叶节点到x的距离一定不同。那么这些不同的距离分别加上x到root的距离也一定不同。
与题目要求不符,所以要满足题目要求,任意一个节点的子树深度必然相同。
证毕。
策略
既然我们要保证每个节点所有子树深度相同,我们可以贪心的处理每个点,把深度用道具强行补到相同。
在dfs的时候,把当前搜索的这个点的子树中最深的深度记为maxdeep。
之后ans += ∑(maxdeep - 这个点的其它子树的深度);
细节看代码吧
Code
#include<iostream>
#include<cstdio>
#include<cctype>
#define int long long//不开LL会66分的
using namespace std; const int MAXN = + ; struct Edge {
int nxt;
int to,w;
} l[MAXN<<]; int n,root,ans;
int head[MAXN],cnt;
int maxdeep[MAXN]; inline int rd() {
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=(ch=='-')?-:;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
} inline void add(int x,int y,int z) {
cnt++;
l[cnt].nxt = head[x];
l[cnt].to = y;
l[cnt].w = z;
head[x] = cnt;
return;
} void dfs(int x,int from) {
int son = maxdeep[x];//提前记一下,因为下面更新要用到原来maxdeep[x]的值,所以用son来记最大的深度
for(int i = head[x];i;i = l[i].nxt) {
if(l[i].to == from) continue;
maxdeep[l[i].to] = maxdeep[x] + l[i].w;
dfs(l[i].to,x);
son = max(son,maxdeep[l[i].to]);
}
maxdeep[x] = son;
for(int i = head[x];i;i = l[i].nxt) {
if(l[i].to == from) continue;
ans += maxdeep[x] - maxdeep[l[i].to];
}
return;
} signed main() {
scanf("%lld%lld",&n,&root);
int x,y,z;
for(register int i = ;i < n;i++) {
x = rd(), y = rd(), z = rd();
add(x,y,z), add(y,x,z);
}
dfs(root,-);
printf("%lld\n",ans);
return ;
}
最新文章
- 【原】如何改变表单元素的外观(for Webkit and IE10)
- XidianOJ 1154 Nhywieza 的串
- C#设计模式(19)——状态者模式(State Pattern)
- Python-操作Memcache、Redis、RabbitMQ、
- C语言 预处理二(宏定义--#define)
- git点滴的积累
- 微信成为首批支持iPhone 6s /Plus 上 3D Touch 功能的 App
- vim配置及插件安装管理(超级详细)
- Directory.GetCurrentDirectory
- How to migrate data from another Mac using Mountain Lion and earlier
- 使用pyton在本地指定目录模拟服务器
- DOM---节点关系
- linux新手记录;可执行文件直接运行
- Hyperledger Fabric channel配置交易
- 有关vue开发的小经验
- pyqt5 窗口无边框和透明
- java-Integer类
- USACO 2012 December ZQUOJ 24122 Scrambled Letters(二分)
- #C语言初学记录(位运算)
- Joyoi花店橱窗(原tyvj1124)