正文

bzoj1827[usaco2010mar]gather奶牛大集会

小飞淙的云端  小飞淙的云端  2022-09-04  748

关键词：

题目描述 Description

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个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。考虑一个由五个农场组成的国家，分别由长度各异的道路连接起来。在所有农场中，3号和4号没有奶牛居住。

输入描述 Input Description

第一行：一个整数N * 第二到N+1行：第i+1行有一个整数C_i * 第N+2行到2*N行，第i+N+1行为3个整数：A_i,B_i和L_i。

输出描述 Output Description

第一行：一个值，表示最小的不方便值。

样例输入 Sample Input

1 1 0 0 2

1 3 1

2 3 2

3 4 3

4 5 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

无

之前的一些废话：

之前做题都懒得写博客，因此欠了一大笔帐，感觉无比的颓废，从现在起写博客也要变成做题的一部分！然后格式全部更新换代了。

题解：

感觉此题跟找重心类似，然而除了递归的求出了子树的信息后没法快速算出父亲以上组成树的答案，然而我们设ans1[now]表示以now为集市的子树答案，这个可以通过递归处理，ms[now]表示now的子树的点权值和，递推的话是这样ans1[now]+= ans1[now]+=(ans1[son]+ms[son]*w)，预处理完了之后我们就可以算出父亲以上组成树的答案了，设ans2[now]表示以now建集市的答案。递推是ans2[now]=ans2[1]+(sum-2*ms[now])*w，然后两次dfs就可以算出结果了。还有一种基于贪心的做法，思想类似,假如now的答案为ans，那么他的儿子答案为ans+(sum-2*ms[now])*w，所以只需要判断sum-2*ms[now]是不是小于0，这样就可以更新最小值了。

代码：（一份是基于贪心的）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define mem(a,b) memset(a,b,sizeof(a))
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
const int maxn=100010;
struct Edge
{
    int u,v,w,next;
    Edge() {}
    Edge(int _1,int _2,int _3,int _4):u(_1),v(_2),w(_3),next(_4) {}
}e[maxn<<1];
int n,ce=-1,a,b,c,first[maxn],A[maxn];
LL ms[maxn],ans1[maxn],ans2[maxn],ans=(LL)1<<50,sum;
void addEdge(int a,int b,int c)
{
    e[++ce]=Edge(a,b,c,first[a]);first[a]=ce;
    e[++ce]=Edge(b,a,c,first[b]);first[b]=ce;
}
void dfs(int now,int fa)
{
    ms[now]=A[now];
    for(int i=first[now];i!=-1;i=e[i].next)
        if(e[i].v!=fa)
        {
            dfs(e[i].v,now);
            ms[now]+=ms[e[i].v];
            ans1[now]+=(ans1[e[i].v]+ms[e[i].v]*(LL)e[i].w);
        }
}
void rdfs(int now,int fa,int w)
{
    if(!fa)ans2[now]=ans1[now];
    else ans2[now]=ans2[fa]+(sum-2ll*ms[now])*(LL)w;
    for(int i=first[now];i!=-1;i=e[i].next)
        if(e[i].v!=fa)rdfs(e[i].v,now,e[i].w);
}
int main()
{
    mem(first,-1);
    n=read();
    for(int i=1;i<=n;i++)A[i]=read(),sum+=A[i];
    for(int i=1;i<n;i++)a=read(),b=read(),c=read(),addEdge(a,b,c);
    dfs(1,0);rdfs(1,0,0);
    for(int i=1;i<=n;i++)ans=min(ans,ans2[i]);
    printf("%lld
",ans);
    return 0;
}

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<cmath>
 6 #include<cstring>
 7 using namespace std;
 8 typedef long long LL;
 9 typedef pair<int,int> PII;
10 #define mem(a,b) memset(a,b,sizeof(a))
11 inline int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
15     while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}
16     return x*f;
17 }
18 const int maxn=100010;
19 struct Edge
20 {
21     int u,v,w,next;
22     Edge() {}
23     Edge(int _1,int _2,int _3,int _4):u(_1),v(_2),w(_3),next(_4) {}
24 }e[maxn<<1];
25 int n,ce=-1,a,b,c,first[maxn],A[maxn];
26 LL ms[maxn],ans1[maxn],ans,sum;
27 void addEdge(int a,int b,int c)
28 {
29     e[++ce]=Edge(a,b,c,first[a]);first[a]=ce;
30     e[++ce]=Edge(b,a,c,first[b]);first[b]=ce;
31 }
32 void dfs(int now,int fa)
33 {
34     ms[now]=A[now];
35     for(int i=first[now];i!=-1;i=e[i].next)
36         if(e[i].v!=fa)
37         {
38             dfs(e[i].v,now);
39             ms[now]+=ms[e[i].v];
40             ans1[now]+=(ans1[e[i].v]+ms[e[i].v]*(LL)e[i].w);
41         }
42 }
43 void rdfs(int now,int fa)
44 {
45     for(int i=first[now];i!=-1;i=e[i].next)
46         if(e[i].v!=fa)
47             if(sum-2*ms[e[i].v]<0)
48             {
49                 ans+=(sum-2*ms[e[i].v])*e[i].w;
50                 rdfs(e[i].v,now);
51             }
52 }
53 int main()
54 {
55     mem(first,-1);
56     n=read();
57     for(int i=1;i<=n;i++)A[i]=read(),sum+=A[i];
58     for(int i=1;i<n;i++)a=read(),b=read(),c=read(),addEdge(a,b,c);
59     dfs(1,0);ans=ans1[1];rdfs(1,0);
60     printf("%lld
",ans);
61     return 0;
62 }

View Code

总结：两次dfs可以弥补一些递归处理没法解决的问题。

嘴巴题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条道路... 查看详情

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

【题解】　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。　　显然选择它的儿子... 查看详情

bzoj_1828_[usaco2010mar]balloc农场分配_线段树

BZOJ_1828_[Usaco2010Mar]balloc农场分配_线段树DescriptionInput第1行：两个用空格隔开的整数：N和M*第2行到N+1行：第i+1行表示一个整数C_i*第N+2到N+M+1行：第i+N+1行表示2个整数A_i和B_iOutput*第一行：一个整数表示最多能够被满足的要求数SampleI... 查看详情

[bzoj1637][usaco2007mar]balancedlineup

1637:[Usaco2007Mar]BalancedLineupTimeLimit:5Sec MemoryLimit:64MBSubmit:693 Solved:460[Submit][Status][Discuss]DescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐查看详情

bzoj1637:[usaco2007mar]balancedlineup

1637:[Usaco2007Mar]BalancedLineupTimeLimit: 5Sec MemoryLimit: 64MBDescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐标(范围:0..1,000,000,000)和种族(0或1)。一直以来FarmerJohn 查看详情

[bzoj]1639:[usaco2007mar]monthlyexpense月度开支

1639:[Usaco2007Mar]MonthlyExpense月度开支TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1077 Solved: 533[Submit][Status][Discuss]DescriptionFarmerJohn是一个令人惊讶的会计学天才，他已经明查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:858 Solved:603[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverystraigh 查看详情

[bzoj1657][usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:863 Solved:607[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverys 查看详情

bzoj1597[usaco2008mar]土地购买

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

bzoj1637[usaco2007mar]balancedlineup*

bzoj1637[Usaco2007Mar]BalancedLineup题意：n头牛，第i头牛位置为ai，种族为bi（只能为0，1），求一个区间（按数轴位置），使得区间两端牛距离差最大且两种种族牛数相等。n≤50000。题解：按位置排序。然后利用前缀和sum[i][0]-sum[j-1][0]... 查看详情

[bzoj1617][usaco2008mar]rivercrossing渡河问题

1617:[Usaco2008Mar]RiverCrossing渡河问题TimeLimit:5Sec MemoryLimit:64MBSubmit:1102 Solved:801[Submit][Status][Discuss]DescriptionFarmerJohn以及他的N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工查看详情

bzoj1597:[usaco2008mar]土地购买

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

bzoj1703:[usaco2007mar]rankingthecows奶牛排名传递闭包,bitset

1703:[Usaco2007Mar]RankingtheCows奶牛排名TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 323 Solved: 238[Submit][Status][Discuss]Description 农夫约翰有查看详情

[bzoj3399][usaco2009mar]sandcastle城堡（排序）

3399:[Usaco2009Mar]SandCastle城堡TimeLimit: 3Sec MemoryLimit: 128MBSubmit: 79 Solved: 66[Submit][Status][Discuss]Description约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻查看详情

[bzoj1639][usaco2007mar]monthlyexpense月度开支

1639:[Usaco2007Mar]MonthlyExpense月度开支TimeLimit:5Sec MemoryLimit:64MBSubmit:1069 Solved:530[Submit][Status][Discuss]DescriptionFarmerJohn是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 867 Solved: 610[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsa 查看详情