hiho 1564 - 简单dfs + 宏的危害!!!
2024-10-21 09:56:05
H公司有 N 台服务器,编号1~N,组成了一个树形结构。其中中央服务器处于根节点,终端服务器处于叶子节点。
中央服务器会向终端服务器发送消息。一条消息会通过中间节点,到达所有的终端服务器。消息每经过一台服务器(包括根节点的中央服务器和叶子节点的终端服务器),就会被处理并存储下来,其中编号为 i 的服务器,执行处理和存储这个过程会花费 Ai 毫秒的时间。消息从一台服务器传输到另一台服务器的时间可以忽略不计。
由于 Ai 各不相同,从中央服务器发出消息到各个终端处理并储存完毕的时间也是不相同的。例如如下的网络,假设1是中央服务器,而2和4是终端服务器。
1
/ \
2 3
|
4
如果A1=1, A2=4, A3=3, A4=2,那么假设1发出消息的时刻是0,终端2处理完的时刻是A1+A2=5,而终端4处理完的时刻是A1+A3+A4=6。
CEO交给小Ho一个任务,要求每台终端处理完消息的时间是完全一致的。小Ho想到了一个天才的解决方案:强行增加某些服务器的处理时间 Ai。例如在上例中,将 A2从4增加到5即可使所有终端都在6毫秒后处理完毕。
当然小Ho希望所有服务器增加的处理时间总和最少。你能帮助小Ho吗?
------------------------------------------------------------------------------------------------------------------------------------
一次遍历,记录每个节点到叶节点的最长路径的长度,以此为依据进行调整。
wa了好几次才找到原因:
//maxc = MAX(maxc,dfs(to));
maxc = std::max(maxc,dfs(to));
开始用的宏定义MAX
#define MAX(a,b) ((a)>=(b)?(a):(b))
相当于调用了两次dfs()。。。。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;
const int N = 1E5+;
struct Edge{
int to;
int next;
};
int cost[N];
LL maxCost[N];
int heads[N];
Edge edgs[N];
bool degree[N];
int eid = ;
LL ans = ;
LL dfs(int id){
LL maxc = ;
for(int cid = heads[id];cid!=-;cid=edgs[cid].next){
int to = edgs[cid].to;
//maxc = MAX(maxc,dfs(to));
maxc = std::max(maxc,dfs(to));
}
for(int cid = heads[id];cid!=-;cid=edgs[cid].next){
int to = edgs[cid].to;
ans += maxc - maxCost[to];
}
return maxCost[id] = maxc+cost[id];
} int main(){
int n,a,b;
while(scanf("%d",&n)!=EOF){
eid = ;
memset(heads,-,sizeof(heads));
memset(degree,false,sizeof(degree));
for(int i=;i<n;i++) scanf("%d",cost+i);
for(int i=;i<n-;i++){
scanf("%d%d",&a,&b); a--,b--;
edgs[eid].to = b;
edgs[eid].next = heads[a];
heads[a] = eid++;
degree[b] = true;
}
int root; for(int i=;i<n;i++) if(!degree[i]) {root=i;break;}
ans = ;
dfs(root);
printf("%lld\n",ans);
}
return ;
}
最新文章
- C# 换行符
- Database事件研究
- Codeforces Round #260 (Div. 1) 	A - Boredom DP
- AngularJS - Apply方法监听model变化
- [LeetCode#110, 112, 113]Balanced Binary Tree, Path Sum, Path Sum II
- 使用RouteDebugger对MVC路由进行调试
- C#中数组,ArrayList与List对象的区别
- pl sql 查询显示乱码解决方法——设置环境变量NLS_LANG
- NHibernate3剖析:Configuration篇之SessionFactory lambda配置
- Java经典编程题50道之四十四
- [bzoj4908][BeiJing2017]开车
- bzoj 3669: [Noi2014]魔法森林 (LCT)
- Java Spring Boot VS .NetCore (五)MyBatis vs EFCore
- JVM笔记(二)JVM基本结构
- 使用BizTalk实现RosettaNet B2B So Easy
- BZOJ3510 首都(LCT)
- java RSA 加签验签【转】
- B - Fuzzy Search (FFT)
- mvc 缓存 sqlCacheDependency 监听数据变化
- LeetCode——4. Median of Two Sorted Arrays
热门文章
- jquery 登录,删除提示信息框
- MyBatis数据持久化(十)与Spring4整合
- c# rc4算法,加密解密类
- 401 - Unauthorized: Access is denied due to invalid credentials.
- GRpc-Go使用笔记
- oracle错误ORA-00604 递归sql级别1出现错误 ora-00942 表或试图不存在 ORA-06512 在line 11
- CorelDRAW 2017通过智能笔触调整自然地绘制草图
- Kattis - Babelfish
- Java语言特点与学习
- 在使用easyui datagrid在tab中遇到的问题