首页 > ACM题库 > HDU-杭电 > HDU 3899-JLUCPC-动态规划-[解题报告]HOJ
2015
04-14

HDU 3899-JLUCPC-动态规划-[解题报告]HOJ

JLUCPC

问题描述 :

Dr. Skywind and Dr. Walkoncloud are planning to hold the annual JLU Collegiate Programming Contest. The contest was always held in the college of software in the past. However, they changed their minds and decided to find the most convenient location from all colleges this year.
Each college in JLU is located in one of the N (1 <= N <= 100,000) different locations (labeled as 1 to N) connected by N-1 roads. Any two colleges are reachable to each other. The Contest can be held at any one of these N colleges. Moreover, Road i connects college A_i and B_i (1 <= A_i <=N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). College i has T_i (0 <= T_i <= 1,000) teams participating in the contest.
When choosing the college to hold the Contest, Dr. Skywind wishes to minimize the inconvenience of the chosen location. The inconvenience of choosing college P is the sum of the distance that all teams need to reach college P (i.e., if the distance from college i to college P is 20, then the travel distance is T_i*20). Please help Dr. Skywind and Dr. Walkoncloud to choose the most convenient location for the contest.

输入:

There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.

输出:

There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.

样例输入:

3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1

样例输出:

4
5

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3899

题意:一棵树,给出每个点的权值和每条边的长度,点j到点i的代价为点j的权值乘以连接i和j的边的长度。求点x使得所有点到点x的代价最小,输出

非常恶心的题目我调试了N久,一直是WA。最后把long long改成了__int64一下就过了,在此鄙视下杭电的编译器

这道题要两次深搜。

1.求出每个节点作为根,他的下面节点到他的花费,以及数量。

2.求出每个节点的兄弟节点到他的花费以及数量。

3.求出每个节点除了他下面的节点的所有节点到他的花费和数量。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
//内存挂
const int maxn=100002;
int n,m,cnt[maxn],tn[maxn];///每个点的人数
__int64 dis[maxn];///最后要求结果
struct node
{
    __int64 dis;
    int v;
}tmp;
vector<node>p[maxn<<1];
void dfs(int u,int fa,__int64 len)
{
    int i,j,v;
    int sum=p[u].size();
    dis[1]+=len*cnt[u];
    tn[u]=cnt[u];
    for(i=0;i<sum;i++)
    {
        int v=p[u][i].v;
        if(v==fa)continue;
        dfs(v,u,len+p[u][i].dis);
        tn[u]+=tn[v];
    }
}
void dfs1(int u,int fa)
{
    int size=p[u].size();
    for(int i=0;i<size;i++)
    {
        int v=p[u][i].v;
        __int64 w=p[u][i].dis;
        if(v==fa) continue;
        dis[v]=dis[u]+(tn[1]-2*tn[v])*w;
         ///对于一条边,求出这条边上面所以边的长度和和下面所有边的长度和,然后就可以进行转移了
        dfs1(v,u);
    }
}
int main()
{
    int u,v,i,j;
    __int64 w;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
          scanf("%d",&cnt[i]);
          dis[i]=0;
          p[i].clear();
        }
        for(i=1;i<n;i++)
        {
            scanf("%d%d %I64d",&u,&v,&w);
            tmp.v=v,tmp.dis=w;
            p[u].push_back(tmp);
            tmp.v=u,tmp.dis=w;
            p[v].push_back(tmp);
        }
        dfs(1,-1,0);
        __int64 ans=dis[1];
        dfs1(1,0);
        for(i=2;i<=n;i++)
        {
            if(ans>dis[i]) ans=dis[i];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}
/*
3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/azheng51714/article/details/8094789


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  4. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience