NOI2011道路修建
Description
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿
意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用， 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。
.jpg)
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建
费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计
算出所需要的费用。请你帮助国王们设计一个这样的软件。
Input
输入的第一行包含一个整数n，表示 W 星球上的国家的数量，国家从 1到n
编号。接下来 n – 1行描述道路建设情况，其中第 i 行包含三个整数ai、bi和ci，表
示第i 条双向道路修建在 ai与bi两个国家之间，长度为ci。
Output
输出一个整数，表示修建所有道路所需要的总费用。
Sample Input
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
Sample Output
20
HINT
n = 1,000,000 1≤ai, bi≤n
0 ≤ci≤ 10^6
题解
神题不解释
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,cnt; int last[1000005],fa[1000005],q[1000005]; ll size[1000005],val[1000005],ans; struct edge{ int to,next,v; }e[2000005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void dp() { int head=0,tail=1; q[0]=1; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].to!=fa[now]) { q[tail++]=e[i].to; fa[e[i].to]=now; val[e[i].to]=e[i].v; } } for(int i=tail-1;i>=0;i--) { int t=q[i]; size[t]++; for(int x=last[t];x;x=e[x].next) if(e[x].to!=fa[t]) size[t]+=size[e[x].to]; ans+=val[t]*abs(size[t]-(n-size[t])); } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } dp(); printf("%lld\n",ans); return 0; } |
Subscribe
计数器 9854630
OI 课件=>
OI 课件=>