USACO[Elite 2010 March Competition/gold]gather

恩,直接DFS,注意用long long int,我就是开始没用long long int,结果错了几次。

思路:

先找一个节点DFS,把树变成有根树,然后统计每个节点的子孙和自己一共有多少牛,记为cow[节点编号],一共有多少牛,记为total_cow,以及全部牛到这个叶子节点所需的花费,记为cost[节点编号]。

然后再DFS,还是从先前找的的叶子开始。

当搜到root时cost[children of root]=cost[root]+(cow_total-cow[children of root])*length(from root to children of root)-cow[children of root])*length(from root to children of root)。

解释:cost[root]是到当前节点集合的费用,如果到孩子那里去集合,那么就要把从孩子哪儿赶来的牛赶回去,所以-cow[children of root])*length(from root to children of root),然后还要把不是在孩子及其子孙那里的牛赶过来,所以+(cow_total-cow[children of root])*length(from root to children of root)。

CODE:

/*

PROG: gather

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-23

DESCRIPTION:

TITLE: Great Cow Gathering [Jeffrey Wang from a contest, 2010]

CONTENT:

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.

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.

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.

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.

PROBLEM NAME: gather

INPUT FORMAT:

* 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

SAMPLE INPUT (file gather.in):

5

1

1

0

0

2

1 3 1

2 3 2

3 4 3

4 5 3

OUTPUT FORMAT:

* Line 1: The minimum inconvenience possible

SAMPLE OUTPUT (file gather.out):

15

*/

#include <stdio.h>

#include <vector>

using std::vector;

 

const long long int oo=1000000000000000000ll;

const int MAXN=100000;

int N;

long long int C[MAXN+1];

long long int A[MAXN-1],B[MAXN-1],L[MAXN-1];

vector<long long int> children[MAXN+1],length[MAXN+1];

long long int total_cow;

long long int cow[MAXN+1];

long long int cost[MAXN+1];

long long int answer;

 

void prepare(int root,int father_of_root=0)

{

     total_cow+=C[root];

     cow[root]+=C[root];

     for (int i=0;i<children[root].size();i++)

         if (children[root][i]!=father_of_root)

         {

            prepare(children[root][i],root);

            cow[root]+=cow[children[root][i]];

            cost[root]+=cost[children[root][i]]

                        +cow[children[root][i]]*length[root][i];

         }

     //printf(“cost and cow of %d : %d %d\n”,root,cost[root],cow[root]);

}

void get_answer(int root,int father_of_root=0)

{

     //printf(“cost of %d: %d\n”,root,cost[root]);

     if (cost[root]<answer) answer=cost[root];

     for (int i=0;i<children[root].size();i++)

         if (children[root][i]!=father_of_root)

         {

            cost[children[root][i]]=cost[root]

                                    +(total_cow-cow[children[root][i]]*2)

                                     *length[root][i];

            get_answer(children[root][i],root);

         }

}

void print(long long int long_long_int)

{

     if (long_long_int>=10)

        print(long_long_int/10);

     printf(“%d”,int(long_long_int%10));

}

 

int main()

{

    freopen(“gather.in”,“r”,stdin);

    freopen(“gather.out”,“w”,stdout);

    scanf(“%d\n”,&N);

    for (int i=1;i<=N;i++)

        scanf(“%d\n”,&C[i]);

    for (int i=0;i<N-1;i++)

        scanf(“%d %d %d\n”,&A[i],&B[i],&L[i]);

   

    for (int i=0;i<N-1;i++)

    {

        children[A[i]].push_back(B[i]);

        children[B[i]].push_back(A[i]);

        length[A[i]].push_back(L[i]);

        length[B[i]].push_back(L[i]);

    }

    int leaf;

    for (int i=1;i<=N;i++)

        if (children[i].size()==1)

        {

           leaf=i;

           break;

        }

    prepare(leaf);

    answer=oo;

    get_answer(leaf);

   

    /*

    printf(“%lld\n”,answer); //for Linux/Unix

    printf(“%I64d\n”,answer); //for Windows

    */

    //for anywhere

    print(answer);

    printf(“\n”);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注