注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

USACO[Elite 2010 March Competition/gold]gather  

2010-04-23 11:23:29|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

恩,直接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;

}

 

  评论这张
 
阅读(691)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018