poj 1849 Two

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

给一颗无根树,用两个人去遍历所有点,最后不必要回到原点,求最小花费

这题其实和hdu 4003是一模一样的,hdu 4003是可以多个机器人,当然也包括2个情况

所以只要拿hdu 4003的代码copy一份就能通过。具体思想就是转化为背包来看待这个问题

当然这题比较特殊,它只有2个车,可以想想 poj 1935 其实又和那题差不多,思想,是完全一样的

1935用一个机器人去遍历特定的点,这题的话,特定的点其实就是全部点,一样的,不过用两个机器人

1935可以知道最后是根到最远的点的路径可以避免走两次,而这里,其实就是树中的最长链可以避免走两次!

(这个很容易想到,不详细证明了)

用背包写

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

struct edge{
int v,w;
edge(){}
edge(int __v,int __w){
v = __v; w = __w;
}
};
vector<edge>e[N];
int n,S,dp[N][3];

void dfs(int u,int fa){
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i].v;
int w = e[u][i].w;
if(v == fa) continue;
dfs(v,u);
for(int k = 2; k >= 1; k--){
int res1 = dp[u][k-1] + dp[v][1] + w;
int res2 = dp[u][k] + dp[v][0] + 2 * w;
dp[u][k] = min(res1,res2);
for(int kk = 1; kk <= k; kk++){
dp[u][k] = min(dp[u][k],dp[u][k-kk]+dp[v][kk] + kk * w);
}
}
dp[u][0] += (dp[v][0] + 2 * w);
}
}

int main(){
while(scanf("%d%d",&n,&S)!=EOF){
for(int i = 1; i <= n; i++){
e[i].clear();
}
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].pb(edge(v,w)); e[v].pb(edge(u,w));
}
cl(dp,0);
dfs(S,-1);
printf("%d\n",dp[S][2]);
}
return 0;
}

减去最长链

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

struct edge{
int v,w;
edge(){}
edge(int __v,int __w){
v = __v; w = __w;
}
};
vector<edge>e[N];
int n,S,dp[N],Max[N][2],maxlink;

void dfs(int u,int fa){
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i].v;
int w = e[u][i].w;
if(v == fa) continue;
dfs(v,u);
if(Max[v][0] + w > Max[u][0]){
Max[u][1] = Max[u][0]; Max[u][0] = Max[v][0] + w;
}
else if(Max[v][0] + w > Max[u][1]){
Max[u][1] = Max[v][0] + w;
}
dp[u] += (dp[v] + 2*w);
}
maxlink = max(maxlink,Max[u][0] + Max[u][1]);
}

int main(){
while(scanf("%d%d",&n,&S)!=EOF){
for(int i = 1; i <= n; i++){
e[i].clear();
}
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].pb(edge(v,w)); e[v].pb(edge(u,w));
}
cl(dp,0); cl(Max,0); maxlink = 0;
dfs(S,-1);
printf("%d\n",dp[S] - maxlink);
}
return 0;
}