基环树DP BZOJ1040 && 牛课暑假多校第二场B discount

╰半夏微凉° 2022-05-19 08:17 133阅读 0赞

思路：基环树就是树多加一条边使之有一个环。基本的思路就是树形dp，只不过它是有环的。当取环上一个元素作为开始点时， 他会对他上一个节点产生影响。所以要想法设法将环破坏掉

[1040骑士][1040]

#include<bits/stdc++.h>
    
    using namespace std;
    typedef long long ll;
    const int N=1000006;
    
    struct node{
        int v, nxt;
    }e[N<<1];
    int n, cnt, head[N], l, r, kd[N<<1], E;
    ll p[N], dp[N][2];
    bool vis[N];
    
    void init(){
        memset(head, -1, sizeof head);
    }
    
    void addEdg(int u, int v, int mk){
        e[cnt].v=v;
        e[cnt].nxt=head[u];
        kd[cnt]=mk;
        head[u]=cnt++;
    }
    
    void dfs(int x, int f){
        vis[x]=true;
    
        for(int i=head[x]; ~i; i=e[i].nxt){
            if(e[i].v==f)
                continue;
            if(vis[e[i].v]){
                l=x; r=e[i].v;
                E=kd[i];
            }
            else
                dfs(e[i].v, x);
        }
    }
    
    void DP(int x, int f){
        dp[x][0]=0; dp[x][1]=p[x];
    
        for(int i=head[x]; ~i; i=e[i].nxt){
            int to=e[i].v;
            if(to==f || kd[i]==E)
                continue;
    
            DP(to, x);
            dp[x][1]+=dp[to][0];
            dp[x][0]+=max(dp[to][0], dp[to][1]);
        }
    
    }
    
    int main()
    {
        init();
        scanf("%d", &n);
    
        for(int i=1; i<=n; i++){
            int to;
            scanf("%lld%d", &p[i], &to);
            addEdg(i, to, i);
            addEdg(to, i, i);
        }
        ll ans=0;
        for(int i=1; i<=n; i++){
            if(vis[i])
                continue;
    
            dfs(i, -1);
            DP(l, -1);
    
            ll mx=dp[l][0];
    
            DP(r, -1);
    
            ans+=max(mx, dp[r][0]);
        }
        printf("%lld\n", ans);
    
        return 0;
    }
    
    /*
    3
    10 2
    20 3
    30 1
    */

[牛课discount][discount]

对于n瓶饮料，每个都有赠送的饮料， 我们如果对这种关系用由赠送的饮料f\[i\]，指向i的一条有向边来构成，那么对于一个点来说，必然会只有一个入度， 一共n条边，所以一定可以形成一个环，也就是说当我们破坏掉环的时候他一定会形成一个树。为了方便，我们可以构建虚拟节点。

原因就是我们在树形dp的时候，肯定需要在环上找一个始发点，但是这个点的状态选择会影响到他的父亲节点，所以我们将他的父亲指向一个替代它的虚拟节点，这个时候就是一个树的结构，这个虚拟结构不需要花费。

最后dp转移方程如代码。

![dp\[i\]\[j\]\[k\]][dp_i_j_k]代表第i个节点用j方式买并且第一个点是k方式买的时候的最小花费。

一共三种方式：0   免费      1  打折     2  赠送

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF=1ll<<60;
    const int N=1e5+10;
    int p[N], d[N], f[N], pre[N], n, root[N], tot=0;
    ll dp[N][3][3];
    vector<ll> G[N], val[N];
    void init(){
        for(int i=1; i<=n; i++)
            pre[i]=i;
        memset(dp, -1, sizeof dp);
    }
    
    int _find(int r){
        return r==pre[r] ? r : pre[r]=_find(pre[r]);
    }
    
    ll dfs(int rt, int way, int ep){
        ll &ret=dp[rt][way][ep];
        if(ret!=-1) return ret;
        ret=INF;
    
        if(rt==n+1){
            if(way==ep)
                return ret=0;//因为递归开始已经将钱加上去了，所以返回0
            else
                return ret=INF;
        }
    
        ll cost=0, sum=0;
        if(way==1) cost=p[rt]-d[rt];
        if(way==2) cost=p[rt];
    
        for(int i=0; i<G[rt].size(); i++){
            int u=G[rt][i];
    
            ll mn=INF;
            for(int j=0; j<3; j++){
                mn=min(mn, dfs(u, j, ep));//选择孩子中三种购买方式最实惠的一种
            }
            sum+=mn;
            val[rt][i]=mn;//记录孩子最小花费
        }
    
        if(way==0){//当该节点是0方式，即免费购买时，需要必须有一个孩子是原价购买
            ll mn=INF;
            for(int i=0; i<G[rt].size(); i++)
                mn=min(mn, sum-val[rt][i]+dp[G[rt][i]][2][ep]);
            ret=mn;
        }
        else
            ret=sum+cost;
    
        return ret;
    }
    
    int main(){
    
        scanf("%d", &n);
        init();
    
        for(int i=1; i<=n; i++)
            scanf("%d", &p[i]);
        for(int i=1; i<=n; i++)
            scanf("%d", &d[i]);
    
        for(int i=1; i<=n; i++){
            scanf("%d", f+i);
            G[f[i]].push_back(i);
            val[f[i]].push_back(0);
            int u=_find(i), v=_find(f[i]);
            if(u==v){
                root[tot++]=i;
            }
            else{
                pre[u]=v;
            }
        }
    
        ll ans=0;
        for(int i=0; i<tot; i++){
            ll mn=INF;
            int u=root[i], v=f[u];
            for(int i=0; i<G[v].size(); i++)
                if(G[v][i]==u) G[v][i]=n+1;//虚拟节点构建
            for(int i=0; i<3; i++){
                mn=min(mn, dfs(u, i, i));
            }
            ans+=mn;
        }
        printf("%lld\n", ans);
        return 0;
    }

[1040]: https://cn.vjudge.net/problem/HYSBZ-1040
[discount]: https://www.nowcoder.com/acm/contest/140/B
[dp_i_j_k]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D%5Bk%5D