M_sea

洛谷2052 道路修建
NOI大水题。。。题目描述在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家之间建设双向道路...
扫描右侧二维码阅读全文
16
2017/11

洛谷2052 道路修建

NOI大水题。。。

题目描述

在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿意修建恰好 n – 1 条双向道路。 每条道路的修建都要付出一定的费用,这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如,在下图中,虚线所示道路两端分别有 2 个、4 个国家,如果该道路长度为 1,则费用为 1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。

P2052

由于国家的数量十分庞大,道路的建造方案有很多种,同时每种方案的修建费用难以用人工计算,国王们决定找人设计一个软件,对于给定的建造方案,计 算出所需要的费用。请你帮助国王们设计一个这样的软件。

传送门

算法

Dfs算出每个节点的子节点数,然后顺便统计答案。

统计答案的话,可以这么想:

断掉查询的边树就分裂成了两部分,一部分是v的子节点数,剩下的是n-v的子节点数
那么减一下就变成了n-v的子节点数*2

然后,记得开long long。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef long long LL;
inline LL read() {
    LL X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
struct Edge { LL v,w,nxt; } e[2000010];
LL head[1000010],cnt;
inline void addEdge(LL u,LL v,LL w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
LL down[1000010];
bool vis[1000010];
LL n,ans=0;
inline void Dfs(LL u) {
    vis[u]=true; down[u]=1;
    for (re LL i=head[u];i;i=e[i].nxt) {
        LL v=e[i].v;
        if (vis[v]) continue;
        Dfs(v); down[u]+=down[v];
        ans+=abs(n-down[v]*2)*e[i].w;
    }
}
int main() {
    n=read();
    for (re LL i=1;i<n;i++) {
        LL u=read(),v=read(),w=read();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    Dfs(1); printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 31 PM

发表评论