bef-> NO.22

Veröffentlicht am

[HNOI/AHOI2018]道路

题目描述

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

W 国的国王小 W 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 W 只能翻修n - 1n−1条道路。小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁 路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利，于是根据人口调 查的数据，小 W 对每个乡村制定了三个参数，编号为ii的乡村的三个参数是a_iai，b_ibi和c_ici。假设 从编号为ii的乡村走到首都一共需要经过xx条未翻修的公路与yy条未翻修的铁路，那么该乡村 的不便利值为

在给定的翻修方案下，每个乡村的不便利值相加的和为该翻修方案的不便利值。 翻修n - 1n−1条道路有很多方案，其中不便利值最小的方案称为最优翻修方案，小 W 自然 希望找到最优翻修方案，请你帮助他求出这个最优翻修方案的不便利值。

输入输出格式

输入格式：

第一行为正整数nn。

接下来n - 1n−1行，每行描述一个城市。其中第ii行包含两个数s_i,t_isi,ti。s_isi表示通向第ii座城市 的公路的起点，t_iti表示通向第i座城市的铁路的起点。如果s_i > 0si>0，那么存在一条从第s_isi座城 市通往第ii座城市的公路，否则存在一条从第-s_i−si个乡村通往第i座城市的公路；t_iti类似地，如 果t_i > 0ti>0，那么存在一条从第t_iti座城市通往第i座城市的铁路，否则存在一条从第-t_i−ti个乡村通 往第ii座城市的铁路。

接下来nn行，每行描述一个乡村。其中第i行包含三个数a_i,b_i,c_iai,bi,ci，其意义如题面所示。

输出格式：

输出一行一个整数，表示最优翻修方案的不便利值。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
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

输出样例#1：

1
54

输入样例#2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

输出样例#2：

1
548

输入样例#3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

输出样例#3：

复制

1
5744902

说明

【样例解释 1】

img

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

一种不便利值等于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。可以证明这是本数据的最优解。

【样例解释 2】

在这个样例中，显然应该翻修所有公路。

【数据范围】 一共20组数据，编号为1 ∼ 20。 对于编号\le 4≤4的数据，n \le 20n≤20；
对于编号为5 ∼ 8的数据，a_i,b_i,c_i \le 5ai,bi,ci≤5，n \le 50n≤50；
对于编号为9 ∼ 12的数据，n \le 2000n≤2000；
对于所有的数据，

内的整数，任意乡村可以通过不超过40条道路到达首都。

题解

首先应该看到最后说不超过40条到首都， 提示我们要将这个东西作为状态。

设

表示i到根需要经过j条没翻修铁路，k条没翻修公路，

然后题目又说通往城市的道路要么修左边要么修右边，这就是很明显的转移了。

对于乡村我们直接计算返回，对于城市看看删左边和右边哪个更优，记忆化搜索即可。

Code：

1
2


一共简短的20行，然而交上去一看居然RE？512MB内存开不了3000w long long？

换种下标（玄学）就可以过了。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 20005
#define LL long long
#define INF 0x7fffffff
struct Node{
    LL a , b , c;
}g[maxn];
LL  n , f[maxn][42][42]  , ans;
int ls[maxn] , rs[maxn];
LL dfs(int x, int k , int p)
{
    if(x >= n) return g[x-n+1].c * (g[x-n+1].a + k) * (g[x-n+1].b + p);
    if(f[x][k][p] != f[0][0][0]) return f[x][k][p];
    return f[x][k][p] = std::min(dfs(ls[x] , k + 1 , p) + dfs(rs[x] , k , p) , dfs(rs[x] , k , p + 1) + dfs(ls[x] , k, p) );
}
int main()
{
    scanf("%lld",&n);
    std::memset(f,0x5f,sizeof(f));
    int x , y , z;
    for(int i = 1 ; i <= n - 1 ; ++i)
    {
        scanf("%d%d",&x,&y);
        if(x < 0) x = n - x - 1;
        if(y < 0) y = n - y - 1;
        ls[i] = x , rs[i] = y;
    }
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld%lld%lld",&g[i].a,&g[i].b,&g[i].c);
    ans = dfs(1 , 0 , 0);
    printf("%lld",ans);
}

有时候树形dp不一定以子树来转移哦。