正文

bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)

Driver_Lao  Driver_Lao  2022-11-02  583

关键词：

【题解】

　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。

　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。

　　显然选择它的儿子作为集合点，它的儿子的子树内的奶牛可以少走当前点到儿子节点的距离dis，不在它儿子的子树内的奶牛要多走dis. 那么我们维护每个节点的子树内的奶牛总数（即点权和），就可以快速进行计算了。效率O(N).

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define N 200010
 4 #define rg register
 5 #define LL long long
 6 using namespace std;
 7 int n,tot,last[N],v[N];
 8 LL ans,sum,size[N],dis[N];
 9 struct edge
10     int to,pre,dis;
11 e[N];
12 inline int read()
13     int k=0,f=1; char c=getchar();
14     while(c<\'0\'||c>\'9\')c==\'-\'&&(f=-1),c=getchar();
15     while(\'0\'<=c&&c<=\'9\')k=k*10+c-\'0\',c=getchar();
16     return k*f;
17 
18 void dfs(int x,int fa)
19     size[x]=v[x];
20     for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa)
21         dis[to]=dis[x]+e[i].dis; 
22         dfs(to,x); size[x]+=size[to];
23     
24 
25 void solve(int x,int fa,LL now)
26     ans=min(ans,now);
27     for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=fa)
28         LL tmp=now-size[to]*e[i].dis+(sum-size[to])*e[i].dis;
29         solve(to,x,tmp);
30     
31 
32 int main()
33     n=read(); 
34     for(rg int i=1;i<=n;i++) v[i]=read(),sum+=v[i];
35     for(rg int i=1;i<n;i++)
36         int u=read(),v=read(),w=read();
37         e[++tot]=(edge)v,last[u],w; last[u]=tot;
38         e[++tot]=(edge)u,last[v],w; last[v]=tot;
39     
40     dfs(1,0);
41     for(rg int i=1;i<=n;i++) ans+=dis[i]*v[i];
42     solve(1,0,ans);
43     printf("%lld\\n",ans);
44     return 0;
45

View Code

洛谷p2986[usaco10mar]伟大的奶牛聚集greatcowgat…

洛谷p2986[usaco10mar]伟大的奶牛聚集（树形动规）

题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，查看详情

bzoj1827[usaco2010mar]gather奶牛大集会*

bzoj1827[Usaco2010Mar]gather奶牛大集会题意：n点树（有边权），找出一个点，使得其它所有点到它的距离和最小。n≤100000。题解：类似bzoj1131，但维护深度和改为维护距离和。代码：1#include<cstdio>2#include<cstring>3#include<algori... 查看详情

bzoj1827:[usaco2010mar]gather奶牛大集会

【算法】树型DP【题解】两遍DFS，第一次得到所有节点子树的路径和，第二次给出除了该子树外其它部分的路径和，时时计算答案。longlong！！！#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#definelllonglongu... 查看详情

嘴巴题4「bzoj1827」[usaco2010mar]gather奶牛大集会

1827:[Usaco2010Mar]gather奶牛大集会DescriptionBessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农... 查看详情

bzoj1827[usaco2010mar]gather奶牛大集会（树形dp）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1827 【题目大意】　　给出一棵有点权和边权的树，　　请确定一个点，使得每个点到这个点的距离乘上该点乘积的总和最小。【题解】　　定1为根，我们先计... 查看详情

bzoj1827[usaco2010mar]gather奶牛大集会

题目描述 Description Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)

p2986[usaco10mar]伟大的奶牛聚集（思维，dp）(代码片段)

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…

典型树上dp，直接暴力算会超时，小心呀 #include<cstring>#include<iostream>#include<algorithm>#include<cstdio>#include<vector>#definemaxn100010usingnamespacestd;typedeflonglongll;structNode intp; lllen; Node(inta,llb):p(a),len(b);vec... 查看详情

ac日记——[usaco10mar]仓配置barnallocation洛谷p1937

[USACO10MAR]仓配置BarnAllocation 思路：　　贪心+线段树维护；代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn100005#defineINF0x3f3f3f3f#definemaxtreemaxn<<2structQueryType{intl,r;booloper 查看详情

p2986[usaco10mar]伟大的奶牛聚集(代码片段)

题意：给一棵n个点的边+点权树，求带权重? 思路：其实这题和之前那个Sta有点像，我们同样只需要预处理出一个f[u]代表以u为集合点的方便程度，那么我们就可以O（1）的转移了假设v是u的儿子，f[v]=f[u]-(siz[v]*len)+(n-siz[v])... 查看详情

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)

　　一道比较经典的题（蒟蒻的我没有一次切掉）……　　首先这道题要优化的原因就是数据范围，要是O(n2) “ 显然 ”会超时。。。　　那么我们很不情愿不得已不开心地最终被迫考虑一下优化（说实话好多算法都... 查看详情

bzoj1597[usaco2008mar]土地购买

[Usaco2008Mar]土地购买TimeLimit:10SecMemoryLimit:162MBDescription农夫John准备扩大他的农场,他正在考虑\(N(1<=N<=50,000)\)块长方形的土地.每块土地的长宽满足\((1<=宽<=1,000,000;1<=长<=1,000,000)\).每块土地的价格是它的面积,但FJ可以同... 查看详情

洛谷p2904[usaco08mar]跨河rivercrossing

P2904[USACO08MAR]跨河RiverCrossing题目描述FarmerJohnisherdinghisNcows(1<=N<=2,500)acrosstheexpansesofhisfarmwhenhefindshimselfblockedbyariver.Asingleraftisavailablefortransportation.FJknowsthathemustr 查看详情

洛谷p2945[usaco09mar]沙堡sandcastle

P2945[USACO09MAR]沙堡SandCastle题目描述FarmerJohnhasbuiltasandcastle!Likeallgoodcastles,thewallshavecrennelations,thatniftypatternofembrasures(gaps)andmerlons(filledspaces);seethediagrambelow.TheN(1<=N&l 查看详情

bzoj1597:[usaco2008mar]土地购买斜率优化

1597:[Usaco2008Mar]土地购买TimeLimit: 10Sec MemoryLimit: 162MBDescription农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价查看详情

动态规划bzoj1584[usaco2009mar]cleaningup打扫卫生

1584:[Usaco2009Mar]CleaningUp打扫卫生TimeLimit:10Sec MemoryLimit:64MBSubmit:511 Solved:349[Submit][Status][Discuss]Description有N头奶牛，每头那牛都有一个标号Pi，1<=Pi<=M<=N<=40000。现在Farm 查看详情