[USACO10MAR]伟大的奶牛聚集

谁践踏了优雅 2021-11-04 22:04 596阅读 0赞

## 题目描述 ##

Bessie is planning the annual Great Cow Gathering for cows all across the country and, of course, she would like to choose the most convenient location for the gathering to take place.

Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

Each cow lives in one of N (1 <= N <= 100,000) different barns (conveniently numbered 1..N) which are connected by N-1 roads in such a way that it is possible to get from any barn to any other barn via the roads. Road i connects barns A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N) and has length L\_i (1 <= L\_i <= 1,000). The Great Cow Gathering can be held at any one of these N barns. Moreover, barn i has C\_i (0 <= C\_i <= 1,000) cows living in it.

每个奶牛居住在 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)只奶牛。

When choosing the barn in which to hold the Cow Gathering, Bessie wishes to maximize the convenience (which is to say minimize the inconvenience) of the chosen location. The inconvenience of choosing barn X for the gathering is the sum of the distances all of the cows need to travel to reach barn X (i.e., if the distance from barn i to barn X is 20, then the travel distance is C\_i\*20). Help Bessie choose the most convenient location for the Great Cow Gathering.

在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C\_i\*20)。帮助Bessie找出最方便的地点来举行大集会。

Consider a country with five barns with \[various capacities\] connected by various roads of varying lengths. In this set of barns, neither barn 3 nor barn 4 houses any cows.

1 3 4 5

@--1--@--3--@--3--@\[2\]

\[1\] |

2 | @\[1\] 2 Bessie can hold the Gathering in any of five barns; here is the table of inconveniences calculated for each possible location:

Gather ----- Inconvenience ------

Location B1 B2 B3 B4 B5 Total

1 0 3 0 0 14 17

2 3 0 0 0 16 19

3 1 2 0 0 12 15

4 4 5 0 0 6 15

5 7 8 0 0 0 15

If Bessie holds the gathering in barn 1, then the inconveniences from each barn are:

Barn 1 0 -- no travel time there!

Barn 2 3 -- total travel distance is 2+1=3 x 1 cow = 3 Barn 3 0 -- no cows there!

Barn 4 0 -- no cows there!

Barn 5 14 -- total travel distance is 3+3+1=7 x 2 cows = 14 So the total inconvenience is 17.

The best possible convenience is 15, achievable at by holding the Gathering at barns 3, 4, or 5.

## 输入输出格式 ##

**输入格式：**

\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer: C\_i

\* Lines N+2..2\*N: Line i+N+1 contains three integers: A\_i, B\_i, and L\_i

第一行：一个整数 N 。

第二到 N+1 行：第 i+1 行有一个整数 C\_i

第 N+2 行到 2\*N 行：第 i+N+1 行为 3 个整数：A\_i,B\_i 和 L\_i。

**输出格式：**

\* Line 1: The minimum inconvenience possible

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

## 输入输出样例 ##

**输入样例\#1：** 复制

5 
    1 
    1 
    0 
    0 
    2 
    1 3 1 
    2 3 2 
    3 4 3 
    4 5 3

**输出样例\#1：** 复制

【解题思路】

一类经典的树形dp问题。

考虑 f\[i\] 表达以i为根子树中奶牛到i的距离和。

第一次dfs从下至上递推出各点的 f\[i\] 和子树奶牛数 siz\[i\]

画图易知每个点的答案 d\[i\] 满足的方程

d[v] = d[u] - siz[v]*a[i].w + (cnt - siz[v])*a[i].w;

通过第二次dfs推得各点的 d\[i\]

显然最小的 d\[i\] 即为答案

【code】

1 #include <cstdio>
     2 #include <cmath>
     3 #include <cstring>
     4 #include <iostream>
     5 #include <algorithm>
     6 #include <stack> 7 using namespace std; 8 struct cow{ 9 int p; 10 long long q; 11 }; 12 stack <cow> S; 13 int h[200005],nxt[200005],endd[200005]; 14 int c[200005],w[200005]; 15 bool v[200005]; 16 long long len[200005],num[200005]; 17 int n,t=0; 18 long long sum=0,ans=999999999999999ll; 19 void zj(int u,int v,int z){ 20 t++; 21 nxt[t]=h[u]; 22 h[u]=t; 23 endd[t]=v; 24 w[t]=z; 25 } 26 void dfs1(int x,int last){ 27 int i; 28 num[x]=c[x]; 29 for(i=h[x];i!=0;i=nxt[i]){ 30 if(endd[i]!=last){ 31 len[endd[i]]=len[x]+w[i]; 32 sum+=len[endd[i]]*c[endd[i]]; 33 dfs1(endd[i],x); 34 num[x]+=num[endd[i]]; 35 } 36 } 37 } 38 void dfs2(int x,long long cost){ 39 int i,a; 40 long long tt,cnt; 41 memset(v,false,sizeof(v)); 42 S.push((cow){x,cost}); 43 v[x]=true; 44 while(!S.empty()){ 45 a=S.top().p; 46 cnt=S.top().q; 47 S.pop(); 48 for(i=h[a];i!=0;i=nxt[i]){ 49 if(v[endd[i]]==false){ 50 tt=cnt-num[endd[i]]*w[i]+(num[1]-num[endd[i]])*w[i]; 51 if(ans>tt) 52 ans=tt; 53 v[endd[i]]=true; 54 S.push((cow){endd[i],tt}); 55 } 56 } 57 } 58 } 59 int main(){ 60 int i,a,b,l; 61 scanf("%d",&n); 62 for(i=1;i<=n;i++) 63 scanf("%d",&c[i]); 64 for(i=1;i<n;i++){ 65 scanf("%d%d%d",&a,&b,&l); 66 zj(a,b,l); 67 zj(b,a,l); 68 } 69 dfs1(1,0); 70 dfs2(1,sum); 71 cout<<ans; 72 return 0; 73 }

转载于:https://www.cnblogs.com/66dzb/p/11240430.html