BZOJ_1827_[Usaco2010 Mar]gather 奶牛大集会_树形DP
2024-08-30 14:36:18
BZOJ_1827_[Usaco2010 Mar]gather 奶牛大集会_树形DP
题意:Bessie正在计划一年一度的奶牛大集会,来自全国各地的奶牛将来参加这一次集会。当然,她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个,这些农场由N-1条道路连接,并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外,每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。在选择集会的地点的时候,Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点,它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和。
分析:
如果对每个点进行dfs,时间复杂度为O(n^2)。我们可以由父节点递推出子节点。对于这道题而言,我们先假设根节点为1,用一遍dfs维护出每个子树的大小。
再推出以其他点为根节点的答案,时间复杂度是O(n)的。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt,n;
LL dis[N],sum[N],ans,niu[N],All,c[N];
inline void add(int u,int v,int w)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
val[cnt]=w;
}
LL dfs1(int x,int y)
{
LL tot=0;
for(int i=head[x];i;i=nxt[i])
{
int t=to[i];
if(t!=y)
{
LL s=dfs1(t,x);
dis[x]+=dis[t]+1ll*val[i]*s;
tot+=s;
}
}
return niu[x]=c[x]+tot;
}
void dfs2(int x,int y)
{
for(int i=head[x];i;i=nxt[i])
{
int t=to[i];
if(t!=y)
{
sum[t]=sum[x]-1ll*niu[t]*val[i]+(All-niu[t])*1ll*val[i];
dfs2(t,x);
}
}
}
int main()
{
ans=1ll<<60;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
All+=c[i];
}
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs1(1,0);
sum[1]=dis[1];
ans=sum[1];
dfs2(1,0);
for(int i=2;i<=n;i++)
{
ans=min(ans,sum[i]);
}
printf("%lld",ans);
}
最新文章
- 构建基于Chromium的应用程序
- hexo deploy出错的解决方法
- 由struts错误使用引发的漏洞,使用参数作为返回的文件路径或文件名,作为返回result 值
- win系统下nodejs安装及环境配置
- 五大要求让BPM与企业对接
- Java获取IP地址:request.getRemoteAddr()注意
- 命令行静态编译QT程序
- uoj164. 【清华集训2015】V 统计
- 移植qt5.3.1到arm
- Android JNI和NDK关系
- Hadoop core-site.xml 配置项列表
- vim忽略大写和小写查找配置
- Shell 流程控制-if for case while until break continue
- tcpdump+wireshark抓包分析
- python处理文件的换行符
- py-day3 python 全局变量和局部变量
- 【转】ssh服务器启动和客户端常用操作
- Oracle安装配置
- mongobooster 的使用
- IOS 怎么用UIScrollView来滚动和缩放他的内容第一篇