牛客网暑期ACM多校训练营（第二场）B discount

链接：https://www.nowcoder.com/acm/contest/140/B
来源：牛客网

题目描述

White Rabbit wants to buy some drinks from White Cloud.
There are n kinds of drinks, and the price of i-th drink is p[i] yuan per bottle.
Since White Cloud is a good friend of White Rabbit, when White Rabbit buys a bottle of i-th drink, White Rabbit can choose only one of the following two discounts :
1.White Rabbit can get a d[i](d[i]<=p[i]) yuan discount. Specifically, White Rabbit only need to pay p[i]-d[i] yuan.
2.White Rabbit can buy a bottle of f[i]-th drink for free(than bonus drink can't use any discount).
White Rabbit wants to have at least a bottle of i-th drink for each i between 1 to n. You need to tell White Rabbit what is the minimal cost.

输入描述:

The first line of input contains an integer n(n<=100000)
In the next line,there are n integers p[1..n] in range [0,1000000000].
In the next line,there are n integers d[1..n] in range [0,1000000000].(d[i]<=p[i])
In the next line,there are n integers f[1..n] in range [1,n].

输出描述:

Print the minimum cost.

示例1

输入

复制

3
10 3 5
5 0 5
1 3 2

输出

复制

8

分析：考虑被赠送的商品->商品，这些商品的赠送关系就形成了基环树森林；
　　　不考虑环，环外树形dp，dp[i][0]表示购买i的子树最小代价，dp[i][1]表示购买i的子树且i以原价购买（考虑到对父亲的赠送）；
　　　那么dp[i][1]可以直接由儿子的dp[j][0]和自身的原价更新到；
　　　dp[i][0]有两种情况，自身被赠送得来或不赠送得来而已；
　　　考虑环上，需要断环为链进行dp,记为g[i][0]和g[i][1],其中g[i]与dp[i]同理；
　　　需要注意的是环上的第一件商品要分是否由最后一件商品赠送而来；
代码：
　　

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,mod=1e9+7,inf=0x3f3f3f3f;
int n,m,k,t,p[maxn],d[maxn],pr[maxn],cir[maxn],tot,vis[maxn];
long long dp[maxn][2],g[maxn][2];
bool iscir[maxn];
vector<int>e[maxn];
void dfs(int x)
{
    if(vis[x]==1)
    {
        int pos=x;
        while(1)
        {
            cir[++tot]=pos;
            iscir[pos]=true;
            pos=pr[pos];
            if(pos==x)return;
        }
    }else if(vis[x]==2)return;
    vis[x]=1;
    for(auto y:e[x])pr[y]=x,dfs(y);
    vis[x]=2;
}
void dfs1(int x)
{
    dp[x][0]=p[x]-d[x];
    dp[x][1]=p[x];
    long long cnt1=0;
    long long cnt2=1e18;
    for(auto y:e[x])
    {
        if(iscir[y])continue;
        dfs1(y);
        dp[x][0]+=dp[y][0];
        dp[x][1]+=dp[y][0];
    }
    for(auto y:e[x])
    {
        if(iscir[y])continue;
        dp[x][0]=min(dp[x][0],dp[x][1]-p[x]-dp[y][0]+dp[y][1]);
    }
}
int main()
{
    int i,j;
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&p[i]);
    for(i=1;i<=n;i++)scanf("%d",&d[i]);
    for(i=1;i<=n;i++)scanf("%d",&j),e[j].push_back(i);
    long long ret=0;
    for(j=1;j<=n;j++)
    {
        if(vis[j])continue;
        tot=0;
        dfs(j);
        if(!tot)continue;
        for(i=1;i<=tot;i++)dfs1(cir[i]);
        if(tot==1){ret+=dp[cir[1]][0];continue;}
        g[1][0]=dp[cir[1]][0],g[1][1]=dp[cir[1]][1];
        for(i=2;i<=tot;i++)
        {
            g[i][0]=min(g[i-1][0]+dp[cir[i]][0],g[i-1][1]+dp[cir[i]][1]-p[cir[i]]);
            g[i][1]=dp[cir[i]][1]+g[i-1][0];
        }
        long long cur=g[tot][0];
        g[1][0]=dp[cir[1]][1]-p[cir[1]];
        g[1][1]=1e18;
        for(i=2;i<=tot;i++)
        {
            g[i][0]=min(g[i-1][0]+dp[cir[i]][0],g[i-1][1]+dp[cir[i]][1]-p[cir[i]]);
            g[i][1]=dp[cir[i]][1]+g[i-1][0];
        }
        ret+=min(cur,g[tot][1]);
    }
    printf("%lld
",ret);
    return 0;
}