[Nowcoder 2018ACM多校第二場B] discount

題目大意： 有n種商品， 價格為p[i]， 購買時可以使用兩種優惠， 一是商品降價d[i]， 另一個是送你一件商品f[i]。 求使得每種商品都至少得到1件的最小花費。 (n≤105,d[i]≤q[i]≤109,f[i]≤n) ( n ≤ 10 5 , d [ i ] ≤ q [ i ] ≤ 10 9 , f [ i ] ≤ n )

題目思路： 對于第二種優惠的贈送關系可以建圖， 連邊f[i]指向i， n個點， n條邊，每個點入度均為1， 構成一個基環樹森林。 考慮普通樹的情況， 令dp[i][0]表示子樹i的最小費用， dp[i][1]表示以第二種優惠購買商品i(即擁有免費獲得其父親點f[i]的權利)的情況下子樹i的最小費用。 按普通的樹形dp來做， 有轉移

dp[u][1]=p[u]+∑v∈son[u]dp[v][0] d p [ u ] [ 1 ] = p [ u ] + ∑ v ∈ s o n [ u ] d p [ v ] [ 0 ]

dp[u][0]=min(p[u]−d[u]+∑v∈son[u]dp[v][0],minx∈son[u]{dp[x][1]+∑v∈son[u]andx!=vdp[v][0]}) d p [ u ] [ 0 ] = m i n ( p [ u ] − d [ u ] + ∑ v ∈ s o n [ u ] d p [ v ] [ 0 ] , m i n x ∈ s o n [ u ] { d p [ x ] [ 1 ] + ∑ v ∈ s o n [ u ] a n d x ! = v d p [ v ] [ 0 ] } )

在考慮有環的情況， 先不管同環上點之間的影響， 先把各個點的挂子樹的值求出來， 最後一次考慮每個環。 可以從環上任一個點斷開為鍊為cir[1…m]， 用g[i][0],g[i][1]類似表示環上第i個點的答案， 考慮鍊上點的轉移有

g[i][1]=dp[cir[i]][1]+g[i−1][0] g [ i ] [ 1 ] = d p [ c i r [ i ] ] [ 1 ] + g [ i − 1 ] [ 0 ]

g[i][0]=min(dp[cir[i]][0]+g[i−1][0],g[i−1][1]+∑v∈son[cir[i]]dp[v][0]) g [ i ] [ 0 ] = m i n ( d p [ c i r [ i ] ] [ 0 ] + g [ i − 1 ] [ 0 ] , g [ i − 1 ] [ 1 ] + ∑ v ∈ s o n [ c i r [ i ] ] d p [ v ] [ 0 ] )

最後枚舉第一個點的狀态來設定其初始值

如果第一個點不是由最後一個點贈送而來則

g[1][0]=dp[cir[1]][0],g[1][1]=dp[cir[1]][1] g [ 1 ] [ 0 ] = d p [ c i r [ 1 ] ] [ 0 ] , g [ 1 ] [ 1 ] = d p [ c i r [ 1 ] ] [ 1 ] ， 取g[m][0]更新答案

如果第一個點是由最後一個點贈送而來則

g[1][0]=∑v∈son[cir[1]]dp[v][0],g[1][1]=dp[cir[1]][1] g [ 1 ] [ 0 ] = ∑ v ∈ s o n [ c i r [ 1 ] ] d p [ v ] [ 0 ] , g [ 1 ] [ 1 ] = d p [ c i r [ 1 ] ] [ 1 ] ， 取g[m][1]更新答案

Code:

#include <map>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define ll long long

const int N = (int) + ;
const ll inf = L << ;

int n;
int cnt, lst[N], nxt[N], to[N], fa[N];

int tim;
int vis[N], incir[N];
vector<int > cir[N]; int m;

int p[N], d[N];

ll ans, f[N][], g[N][], sum[N]; bool root[N];

void add(int u, int v){
    nxt[++ cnt] = lst[u]; lst[u] = cnt; to[cnt] = v;
}

void dfs(int u){
    vis[u] = tim;

    for (int j = lst[u]; j; j = nxt[j]){
        int v = to[j];

        if (vis[v] == tim){
            m ++;
            int p = u;
            for (; p != v; p = fa[p]){
                cir[m].push_back(p);
                incir[p] = ;
            }
            cir[m].push_back(p);
            incir[p] = ;
            continue;
        }

        fa[v] = u;
        if (!vis[v]) dfs(v);
    }

}

void dp(int u){
    vis[u] = ;

    for (int j = lst[u]; j; j = nxt[j]){
        int v = to[j];

        if (!vis[v]) dp(v);

        if (incir[v]) continue;
        sum[u] += f[v][];
    }

    f[u][] = p[u] + sum[u];
    f[u][] = p[u] + sum[u] - d[u];
    for (int j = lst[u]; j; j = nxt[j]){
        int v = to[j];

        if (incir[v]) continue;

        f[u][] = min(f[u][], f[v][] + sum[u] - f[v][]);
    }
}

int main(){
    scanf("%d", &n);
    for (int i = ; i <= n; i ++) scanf("%d", p + i);
    for (int i = ; i <= n; i ++) scanf("%d", d + i);
    for (int i = , x; i <= n; i ++) scanf("%d", &x), add(x, i);

    for (int i = ; i <= n; i ++)
        if (!vis[i]) {++ tim; dfs(i);}

    memset(vis, , sizeof(vis));

    for (int i = ; i <= n; i ++)
        if (!vis[i]) dp(i);

    for (int i = ; i <= m; i ++){
        ll ret = inf;
        int sz = cir[i].size();

        g[][] = f[cir[i][]][], g[][] = f[cir[i][]][];

        for (int j = ; j < sz; j ++){
            g[j][] = f[cir[i][j]][] + g[j - ][]; 
            g[j][] = min(f[cir[i][j]][] + g[j - ][], g[j - ][] + sum[cir[i][j]]);
        }

        ret = min(ret, g[sz - ][]);

        g[][] = sum[cir[i][]]; g[][] = f[cir[i][]][];
        for (int j = ; j < sz; j ++){
            g[j][] = f[cir[i][j]][] + g[j - ][]; 
            g[j][] = min(f[cir[i][j]][] + g[j - ][], g[j - ][] + sum[cir[i][j]]);
        }

        ret = min(ret, g[sz - ][]);

        ans += ret;
    }

    printf("%lld\n", ans);

    return ;
}