Description
在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿
意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用, 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如,在下图中,虚线所示道路两端分别有 2 个、4个国家,如果该道路长度为 1,则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。
由于国家的数量十分庞大,道路的建造方案有很多种,同时每种方案的修建
费用难以用人工计算,国王们决定找人设计一个软件,对于给定的建造方案,计
算出所需要的费用。请你帮助国王们设计一个这样的软件。
Solution
比较难,需要用到DFS算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
int n,num=0,head[N],nxt[N<<1],to[N<<1],dis[N<<1];
inline void link(int x,int y,int z){
nxt[++num]=head[x];to[num]=y;dis[num]=z;head[x]=num;
}
int f[N];ll ans=0;
inline void dfs(int x,int last){
f[x]=1;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==last)continue;
dfs(u,x);
f[x]+=f[u];
ans+=1ll*abs(n-f[u]-f[u])*dis[i];
}
}
void work(){
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
link(x,y,z);link(y,x,z);
}
dfs(1,1);
cout<<ans<<endl;
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
work();
return 0;
}
bzoj 2435: [Noi2011]道路修建的更多相关文章
-
bzoj 2435: [Noi2011]道路修建 树上 dp
2435: [Noi2011]道路修建 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/pr ...
-
BZOJ 2435: [Noi2011]道路修建( dfs )
NOI的水题...直接一遍DFS即可 ------------------------------------------------------------------------- #includ ...
-
BZOJ 2435: [Noi2011]道路修建 dfs搜图
2435: [Noi2011]道路修建 Description 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他 ...
-
bzoj 2435: [Noi2011]道路修建【树形dp】
dp求size和deep,然后对每条边模拟求代价即可 #include<iostream> #include<cstdio> #include<algorithm> ...
-
2435: [Noi2011]道路修建
2435: [Noi2011]道路修建 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2188 Solved: 639[Submit][Status ...
-
2435: [Noi2011]道路修建(树上操作)
2435: [Noi2011]道路修建 题目:传送门 题解: 建完边之后以1为根建树,统计深度和各个点的子树大小(包括自己) 询问的时候:答案=长度*abs(n-深度大的点的子树大小*2) ans+= ...
-
【BZOJ】2435: [Noi2011]道路修建(树形dp)
http://www.lydsy.com/JudgeOnline/problem.php?id=2435 我怎么感觉那么水.. 坑的是,dfs会爆...好吧..用bfs.. //upd:我的智商也是醉 ...
-
2435: [Noi2011]道路修建 - BZOJ
Description 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿意修建恰好 n – 1条双向道路. ...
-
BZOJ 2435 NOI2011 道路建设 BFS/DFS
标题效果:给定一个树(直接将树.不要贪图生成树图!).寻找每条边权值*分差的两侧之间 BFS水必须是能 竟DFS能够住...系统堆栈可能有些不够,我们可以使用内联汇编手册中大型系统堆栈 详见代码 这个 ...
随机推荐
-
微信小程序开发初探
一.关于微信小程序 1.1 小程序诞生的背景 张小龙说道: (1)一切以用户价值为依归→用户是微信的核心,所以微信中没有很多与客户无关的功能,比如QQ中的乱七八糟一系列东西. (2)让创造发挥价值→所 ...
-
20150912华为机考2之";输入一段字符串(英文),将每个单词首字母大写后输出";
还有其他一些(隐性)要求(要不然无法通过测试): .如果首字母已经大写,则不用变 .不是英文字母的不变 e.g. Input: hello world! this is _Ljj speaking! ...
-
linux下Gnome桌面环境的安装
在实际工作中,无论是生产环境还是公司内部环境.很多时候装的linux系统都是最小化安装的.即没有桌面环境, 那么如果有时我们又需要一个桌面环境.该怎么安装呢?其实不难,现笔者将安装方法分享如下. 测试 ...
-
M1分数分配
进过第一轮迭代我们依据工作量及质量决定分配分数方案: 王皓南 24.5分 黄宇冰 24分 申开亮 23.5分 许晋 21分 王宇杰 17分 吴润凡 16分 巴丹益昔 14分
-
在objc项目中使用常量的最佳实践
在objc项目中使用常量的最佳实践 之前,在在objc项目中使用常量中,使用c的预处理#define来设置常量.比如,可以做个头文件,然后在需要的类文件中import,使用常量. 但这不是最佳实践 ...
-
移动前端之viewport
在移动设备上进行网页的重构或开发,首先得搞明白的就是移动设备上的viewport了,只有明白了viewport的概念以及弄清楚了跟viewport有关的meta标签的使用,才能更好地让我们的网页适配或 ...
-
(转载)Jython 简单入门
转载链接:http://willzh.iteye.com/blog/307222 1. 用Jython调用Java类库 第一步.创建Java类 写一个简单的Java类,用Point来示例: impor ...
-
使用angular4搭建博客(一)
本文长期更新,未经运行,严禁转载. 博客(制作中) http://101.200.58.228/ Github https://github.com/Teloi/TEIndex 框架选择 Angula ...
-
React Router 使用教程
一.基本用法 React Router 安装命令如下. $ npm install -S react-router 使用时,路由器Router就是React的一个组件. import { Router ...
-
MSB4064 错误
把项目从vs2008转成vs 2012 后,受用msbuild 编译出错 错误Code:MSB4064 修改 把msbuild 的路径从 %windir%\Microsoft.NET\Framewor ...