少鸽 OST+ 剧中歌 vol2 双倍的快乐

Problem

https://www.luogu.org/problemnew/show/P3577

Solution

考虑生成 dfs 树。

无向图中生成 dfs 树中有一个重要的性质，就是没有横叉边和后向边，只有前向边。

这样的性质下直接考虑在 dfs 树上以 dfs 序进行状压 dp。三进制状压：0 为选，1 为不选 + 没有相邻，2 为不选 + 相邻。

状态：$f_{i,j}$ dfs 序中第 $i$ 位的到根的状态为 $j$ 。为了方便实现，我们把第一维省去，把第一维看做深度来进行 dp。

那么有两种转移，就是选或者不选这个点。

如果选择这个点，则需要将现在到根状态的为 $1$ 的相连前向边的节点状态全部变成 $2$。

如果不选择这个点，则需要判断这个点的状态是 $1$ 还是 $2$。

这样的话直接 dfs 做 dp，回溯的话记得合并（事实上还是一个 dfs 序的 dp 顺序，但是方便多了）。

Code

// Code by ajcxsu
// Problem: tur

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=2e4+10, M=1e5+10;
int h[N], h2[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
inline void ins2(int a, int b) { nexp[p]=h2[a], h2[a]=p, to[p]=b, p++; }
int c[N];

int U=1;
int dfn[N], idx;
void dfs(int x) {
    dfn[x]=++idx;
    for(int u=h[x];u;u=nexp[u]) if(!dfn[to[u]]) ins2(x, to[u]), dfs(to[u]);
}

const int G=1e5+10;
int po[12], d[N];
char vis[N];
int f[12][G];

void dfs(int x, int dep) {
    vis[x]=1, d[x]=dep;
    if(dep) {
        int tem[N], t=0;
        for(int u=h[x];u;u=nexp[u])
            if(vis[to[u]]) tem[++t]=po[d[to[u]]];
        for(int i=0;i<po[dep+1];i++) f[dep][i]=INF;
        int U, V;
        for(int i=0;i<po[dep];i++) {
            U=1, V=i;
            for(int j=1;j<=t;j++) {
                if(i/tem[j]%3==0) U=2;
                else if(i/tem[j]%3==1) V+=tem[j];
            }
            f[dep][i+U*po[dep]]=min(f[dep][i+U*po[dep]], f[dep-1][i]);
            f[dep][V]=min(f[dep][V], f[dep-1][i]+c[x]);
        }
    }
    else f[0][0]=c[x], f[0][1]=0, f[0][2]=INF;
    for(int u=h[x];u;u=nexp[u]) if(!vis[to[u]]) {
        dfs(to[u], dep+1);
        for(int i=0;i<po[dep+1];i++)
            f[dep][i]=min(f[dep+1][i+2*po[dep+1]], f[dep+1][i]);
    }
}


int main() {
    po[0]=1;
    for(int i=1;i<12;i++) po[i]=po[i-1]*3;
    int n, m;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) gn(c[i]);
    int u, v, ans=0;
    for(int i=0;i<m;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i, 0), ans+=min(f[0][0], f[0][2]);
    printf("%d\n", ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3577.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆