P2986 [USACO10MAR]伟大的奶牛聚集Great Cow Gat…

￡神魔★判官ぃ 2021-11-26 07:20 254阅读 0赞

## 题目描述 ##

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

每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场Ai和Bi(1 <= Ai<=N; 1 <= Bi <= N),长度为Li(1 <= Li <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者Ci(0 <= Ci <= 1,000)只奶牛。

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

## 输入输出格式 ##

**输入格式：**

第一行：一个整数 N 。

第二到 N+1 行：第 i+1 行有一个整数 Ci

第 N+2 行到 2\*N 行：第 i+N+1 行为 3 个整数：Ai，Bi和 Li。

**输出格式：**

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

## 输入输出样例 ##

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

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

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

## 代码 ##

本题有两种解决方法

**1.二次扫描，换根法**

先求出某一点不方便度，通过转移root

那么**f\[to\]=f\[u\]-s\[to\]\*e\[i\].val+(sum-s\[to\])\*e\[i\].val**;

其中**f**表示不方便度，**s\[to\]**表示子树牛数，**sum-s\[to\]**表示子树父节点的牛数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=100000+100;
    int head[maxn];
    long long p[maxn],f[maxn],s[maxn];
    long long sum,ans;
    struct edge
    {
        int to,next;
        long long val;
    }e[maxn<<2];
    int size=0;
    inline long long read()
    {
        long long x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
           if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
        return x*f;
    }
    void addedge(int u,int v,long long w)
    {
        e[++size].to=v;e[size].val=w;e[size].next=head[u];head[u]=size;
    }
    void dfs1(int u,int fa)
    {
        for(int i=head[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(to==fa)continue;
            dfs1(to,u);
            f[u]+=f[to]+s[to]*e[i].val;
            s[u]+=s[to];
        }
        s[u]+=p[u];
    }
    void dfs2(int u,int fa)
    {
        for(int i=head[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(to==fa)continue;
            f[to]=f[u]-s[to]*e[i].val+(sum-s[to])*e[i].val;
            dfs2(to,u);
        }
    }
    int main()
    {
        int n=read();
        for(int i=1;i<=n;i++)
        s[i]=read(),sum+=s[i];
        for(int i=1;i<n;i++)
        {
            int u=read(),v=read();
            long long w=read();
            addedge(u,v,w);
            addedge(v,u,w);
        }
        dfs1(1,0);
        ans=f[1];
        dfs2(1,0);
        for(int i=1;i<=n;i++)
        ans=min(ans,f[i]);
        printf("%lld\n",ans);
        return 0;
    }

**2.树的重心**

**定义**

树的重心：子树中最大的子树节点数最少的点,删去重心后，生成的多棵树尽可能平衡。

树的重心具有一下性质

**1 ：树中所有点到重心的距离和是最小的，一棵树最多有两个重心**

2 ：把两棵树通过加一条边得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上

3 ：一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置

由性质1我们可以想到树的重心的解法，猜想该点，在树的重心上

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=100000+100;
    int head[maxn];
    long long p[maxn],d[maxn],ms[maxn],s[maxn];
    int g=1;
    long long sum,ans;
    struct edge
    {
        int to,next;
        long long val;
    }e[maxn<<2];
    int size=0;
    inline long long read()
    {
        long long x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
           if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
        return x*f;
    }
    void addedge(int u,int v,long long w)
    {
        e[++size].to=v;e[size].val=w;e[size].next=head[u];head[u]=size;
    }
    void dfs1(int u,int fa)
    {
        s[u]=p[u];
        for(int i=head[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(to==fa)continue;
            dfs1(to,u);
            s[u]+=s[to];
            ms[u]=max(ms[u],s[to]);
        }
        ms[u]=max(ms[u],sum-s[u]);
    }
    void dfs2(int u,int fa)
    {
        for(int i=head[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(to==fa)continue;
            d[to]=d[u]+e[i].val;
            ans+=d[to]*p[to];
            dfs2(to,u);
        }
    }
    int main()
    {
        int n=read();
        for(int i=1;i<=n;i++)
        p[i]=read(),sum+=p[i];
        for(int i=1;i<n;i++)
        {
            int u=read(),v=read();
            long long w=read();
            addedge(u,v,w);
            addedge(v,u,w);
        }
        dfs1(1,0);
        for(int i=2;i<=n;i++)
        if(ms[i]<ms[g])g=i;
        dfs2(g,0);
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/DriverBen/p/10926433.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211126/924a48f636254bb0a0882975e9805ef4.png