转载请注明出处:http://tokitsukaze.live/

题目链接:https://www.nowcoder.com/acm/contest/140/B


题意:有n种饮料,你可以选择一下两种优惠策略
1、打折购买,花费为p[x]-d[x]
2、原价购买,但是会赠送给你一瓶类型为f[x]的饮料
问你获得全部种类的饮料的最小花费为多少


题解(solved by winterzz1):
根据题意,可以建立从购买饮料到赠送饮料的有向边。建出的图每一个联通块都是一颗树多一条边。
先预处理,枚举每一条边,如果两端点u,v还不在同一个联通块中,就把起点u与终点v用并查集并起来。否则记u为root,v为对应的ex节点,同时删去这条边,将图改造为树。
例如
1

加入的边为
5 1
2 5
2 4
2 3
6 7
6 2

那么在最后加入6->2这条边时,由于2,6已经属于同一个联通块,就记6为root,2为对应的ex节点。

因为整个图可能是不连通的,所以可能会产生多个root节点和对应的ex节点。

这样做完以后原图就被改造成了由多个树组成的森林。

先简化题目,不考虑root节点对ex节点的影响。

那么就是树形dp。dp数组两个维度dp[x][0]表示第x节点赠送父节点的最优解,dp[x][1]表示第x节点不赠送父节点的最优解。

dp[x][0]=min(p[x]-d[x]+Σdp[ch][0],dp[k][1]-dp[k][0]+ Σdp[ch][0])k∈ch。

对于dp[x][1]直接做一步贪心,因为赠送父节点就必须原价购买,而原价购买的价格一定高于其他情况。

dp[x][1]= p[x]+ Σdp[ch][0]。

现在考虑root节点对ex节点的影响,再扩个维度dp[x][k][0]表示root节点没有提供ex节点的饮料,dp[x][k][1]表示root节点提供了ex节点的饮料。

显然第三个维度仅仅对当前节点为ex节点时才有影响,否则这个维度无用。

那么如果当前节点不是ex节点,按照二维直接做,0转移到0,1转移到1即可。

即:
dp[x][0][0]=min(p[x]-d[x]+Σdp[ch][0][0],dp[k][1][0]-dp[k][0][0]+ Σdp[ch][0][0])k∈ch。

dp[x][0][1]=min(p[x]-d[x]+Σdp[ch][0][1],dp[k][1][1]-dp[k][0][1]+ Σdp[ch][0][1])k∈ch。

如果当前节点为ex节点,需要特殊转移。
dp[ex][0][0]=min(p[root]-d[root]+ Σdp[ch][0][0] dp[k][1][0]-dp[k][0][0]+ Σdp[ch][0][0]) k∈ch。

dp[ex][0][1]= Σdp[ch][0][1](贪心,如果根节点提供ex节点的饮料,就不需要子树再提供)

dp[ex][1][0]= Σdp[ch][0][0]+p[root]
dp[ex][1][1]= Σdp[ch][0][1]+p[root]

注意转移到最后dp[root][0][1]和dp[root][1][0]是自相矛盾的非法状态,合法的只有dp[root][0][0]和dp[root][1][1],所以答案为min(dp[root][0][0], dp[root][1][1])。

代码:

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int fa[MAXN],f[MAXN],root[MAXN],ex[MAXN],tot,n;
long long ans,p[MAXN],d[MAXN],dp[MAXN][2][2];
vector<int> G[MAXN];
int findf(int x)
{
if(x==fa[x])return x;
return fa[x]=findf(fa[x]);
}
void unions(int x,int y)
{
if(findf(x)!=findf(y))
{
fa[findf(x)]=findf(y);
}
return;
}
void dp_dfs(int root,int ex)
{
long long sum00=0;
long long sum01=0;
for(int i=0;i<G[root].size();++i)
{
dp_dfs(G[root][i],ex);
sum00+=dp[G[root][i]][0][0];
sum01+=dp[G[root][i]][0][1];
}
if(root==ex)
{
dp[root][0][0]=sum00+p[root]-d[root];
dp[root][0][1]=sum01;
dp[root][1][0]=sum00+p[root];
dp[root][1][1]=sum01+p[root];
for(int i=0;i<G[root].size();++i)
{
dp[root][0][0]=min(dp[root][0][0],sum00-dp[G[root][i]][0][0]+dp[G[root][i]][1][0]);
}
}
else
{
dp[root][0][0]=sum00+p[root]-d[root];
dp[root][0][1]=sum01+p[root]-d[root];
dp[root][1][0]=sum00+p[root];
dp[root][1][1]=sum01+p[root];
for(int i=0;i<G[root].size();++i)
{
dp[root][0][0]=min(dp[root][0][0],sum00-dp[G[root][i]][0][0]+dp[G[root][i]][1][0]);
dp[root][0][1]=min(dp[root][0][1],sum01-dp[G[root][i]][0][1]+dp[G[root][i]][1][1]);
}
}
return;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
ans=0;
tot=0;
for(int i=1;i<=n;++i)
{
scanf("%lld",&p[i]);
dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=0;
G[i].clear();
fa[i]=i;
}
for(int i=1;i<=n;++i)
{
scanf("%lld",&d[i]);
}
for(int i=1;i<=n;++i)
{
scanf("%lld",&f[i]);
if(findf(i)!=findf(f[i]))
{
G[f[i]].push_back(i);
unions(f[i],i);
}
else
{
root[++tot]=i;
ex[tot]=f[i];
}
}
for(int i=1;i<=tot;++i)
{
dp_dfs(root[i],ex[i]);
ans+=min(dp[root[i]][0][0],dp[root[i]][1][1]);

}
printf("%lld\n",ans);
}
return 0;
}