【Bzoj5290】【Luogu4438】Hnoi2018道路

Source and Judge

Hnoi2018
Bzoj5290
Luogu4438

Problem

【Description】
W 国的交通呈一棵树的形状。W 国一共有 n - 1 个城市和 n 个乡村,其中城市从 1 到 n−1 编号,乡村从 1 到 n 编号,且 1 号城市是首都。道路都是单向的,本题中我们只考虑从乡村通往首都的道路网络。对于每一个城市,恰有一条公路和一条铁路通向这座城市。对于城市i, 通向该城市的道路(公路或铁路)的起点,要么是一个乡村,要么是一个编号比 i 大的城市。 没有道路通向任何乡村。除了首都以外,从任何城市或乡村出发只有一条道路;首都没有往 外的道路。从任何乡村出发,沿着唯一往外的道路走,总可以到达首都。

W 国的国王小 W 获得了一笔资金,他决定用这笔资金来改善交通。由于资金有限,小 W 只能翻修 n−1 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路,即从公路和铁 路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利,于是根据人口调 查的数据,小 W 对每个乡村制定了三个参数,编号为 i 的乡村的三个参数是a,b,c 。假设 从编号为 i 的乡村走到首都一共需要经过 x 条未翻修的公路与 y 条未翻修的铁路,那么该乡村 的不便利值为(a+x)×(b+y)×c。在给定的翻修方案下,每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修 n−1 条道路有很多方案,其中不便利值最小的方案称为最优翻修方案,小 W 自然希望找到最优翻修方案,请你帮助他求出这个最优翻修方案的不便利值。
【Input】
第一行为正整数 n 。
接下来 n−1 行,每行描述一个城市。其中第 i 行包含两个数 si,ti 。si 表示通向第 i 座城市 的公路的起点,ti 表示通向第i座城市的铁路的起点。如果si>0 ,那么存在一条从第si 座城 市通往第 i 座城市的公路,否则存在一条从第 −si个乡村通往第i座城市的公路; ti 类似地,如 果 ti>0 ,那么存在一条从第 ti 座城市通往第i座城市的铁路,否则存在一条从第 −ti 个乡村通 往第 i 座城市的铁路。
接下来 n 行,每行描述一个乡村。其中第i行包含三个数 a,b,c,其意义如题面所示。
【Output】
输出一行一个整数,表示最优翻修方案的不便利值。
【Limited conditions】
n≤20000,1≤ai,bi≤60,1≤ci≤10^9,任意乡村可以通过不超过40条道路到达首都。
【Sample input 1】
6
2 3
4 5
-1 -2
-3 -4
-5 -6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【Sample output 1】
54
【Sample input 2】
9
2 -2
3 -3
4 -4
5 -5
6 -6
7 -7
8 -8
-1 -9
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
1 60 1
【Sample output 2】
548
【Sample input 3】
12
2 4
5 3
-7 10
11 9
-1 6
8 7
-6 -10
-9 -4
-12 -5
-2 -3
-8 -11
53 26 491
24 58 190
17 37 356
15 51 997
30 19 398
3 45 27
52 55 838
16 18 931
58 24 212
43 25 198
54 15 172
34 5 524
【Sample output 3】
5744902
【Sample explanation】

如图所示,我们分别用蓝色、黄色节点表示城市、乡村;用绿色、红色箭头分别表示 公路、铁路;用加粗箭头表示翻修的道路。

一种不便利值等于54的方法是:翻修通往城市2和城市5的铁路,以及通往其他城市的 公路。用→和⇒表示公路和铁路,用∗→和∗⇒表示翻修的公路和铁路,那么:

编号为1的乡村到达首都的路线为:-1 ∗→ 3 ⇒ 1,经过0条未翻修公路和1条未翻修铁 路,代价为3 × (1 + 0) × (2 + 1) = 9;
编号为2的乡村到达首都的路线为:-2 ⇒ 3 ⇒ 1,经过0条未翻修公路和2条未翻修铁 路,代价为2 × (1 + 0) × (3 + 2) = 10;
编号为3的乡村到达首都的路线为:-3 ∗→ 4 → 2 ∗→ 1,经过1条未翻修公路和0条未 翻修铁路,代价为3 × (2 + 1) × (1 + 0) = 9;
编号为4的乡村到达首都的路线为:-4 ⇒ 4 → 2 ∗→ 1,经过1条未翻修公路和1条未翻 修铁路,代价为1 × (2 + 1) × (3 + 1) = 12;
编号为5的乡村到达首都的路线为:-5 → 5 ∗⇒ 2 ∗→ 1,经过1条未翻修公路和0条未 翻修铁路,代价为2 × (3 + 1) × (1 + 0) = 8;
编号为6的乡村到达首都的路线为:-6 ∗⇒ 5 ∗⇒ 2 ∗→ 1,经过0条未翻修公路和0条未翻修铁路,代价为1 × (3 + 0) × (2 + 0) = 6;

总的不便利值为9 + 10 + 9 + 12 + 8 + 6 = 54。可以证明这是本数据的最优解。

Record

30min

Analysis

请先思考

好菜啊,没想到记忆化,考试的时候打了个暴力
主要是自己傻傻地把边拉出来决策……这样就根本不会联想到记忆化好吧

听说这个题当初省选现场没有省队大爷AC……
这道题的精髓就在于,把2^n的大暴力通过记忆化变成了精悍的树形dp

Code

请先思考
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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
ll mymin(ll x,ll y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=21000;
//*******************全局定义*******************
struct Nod
{
int lc,rc;
}a[MAXN];
struct Xj
{
ll a,b,c;
}b[MAXN];
ll f[MAXN][41][41];
//*******************实现*******************
ll solve(int now,ll x,ll y)
{
if(now<0) return (b[-now].a+x)*(b[-now].b+y)*b[-now].c;
if(f[now][x][y]<f[0][0][0]) return f[now][x][y];
return f[now][x][y]=mymin(
solve(a[now].lc,x,y)+solve(a[now].rc,x,y+1),
solve(a[now].lc,x+1,y)+solve(a[now].rc,x,y)
);
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
int n;scanf("%d",&n);
for(int i=1;i<=n-1;i++) scanf("%d%d",&a[i].lc,&a[i].rc);
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&b[i].a,&b[i].b,&b[i].c);
memset(f,63,sizeof(f));
printf("%lld",solve(1,0,0));
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/Hnoi2018道路.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%