JZOJ 5442 荒诞

发表于 | 分类于 | 11

看到某个限制，直接考虑建出 DFS 树，则深度不超过 10。

从而考虑在 DFS 序上 DP，设 fu,S 表示当前考虑到 u，DFS 序在 u 之前的除了 u 到根的链上的结点都被覆盖，u 到根的链上按深度的状态为 S。
这是一个三进制状态。三个值分别代表没有选也没有被覆盖 / 没有选但被覆盖 / 选了。
从而按照 DFS 序推过去就可以了。

如果是在 DFS 的时候计算直接计算可能在回溯时更新父亲会更加自然（即题解提到的欧拉序）。
不过我偷懒直接在 DFS 序上推了。

注意卡常。

代码： 

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4;
const int M = 2.5e4;
const int D = 10;
const int S = 59049;
int n,m;
int a[N + 5];
int to[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[tot] = v,pre[tot] = first[u],first[u] = tot++;
}
int pw[D + 5],full;
int fa[N + 5],efa[N + 5],dep[N + 5];
int F[D + 5][N + 5];
int back[N + 5];
int id[N + 5],rk[N + 5],sz[N + 5];
int s[N + 5],top,tot;
int f[2][S + 5];
int ans;
void dfs(int p)
{
    rk[id[p] = ++tot] = p,sz[p] = 1;
    s[++top] = p;
    for(register int i = 1;i <= top;++i)
        F[i][p] = s[i];
    for(register int i = first[p];~i;i = pre[i])
        if(!id[to[i]])
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,efa[to[i]] = i,
            dfs(to[i]),
            sz[p] += sz[to[i]];
        else if(id[to[i]] < id[p])
            back[p] |= 1 << dep[to[i]] - 1;
    --top;
}
inline int check(int s,int l,int r)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4;
const int M = 2.5e4;
const int D = 10;
const int S = 59049;
int n,m;
int a[N + 5];
int to[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[tot] = v,pre[tot] = first[u],first[u] = tot++;
}
int pw[D + 5];
int fa[N + 5],efa[N + 5],dep[N + 5];
int F[D + 5][N + 5];
int back[N + 5];
int id[N + 5],rk[N + 5],sz[N + 5];
int s[N + 5],top,tot;
int f[2][S + 5];
int ans;
void dfs(int p)
{
    rk[id[p] = ++tot] = p,sz[p] = 1;
    s[++top] = p;
    for(register int i = 1;i <= top;++i)
        F[i][p] = s[i];
    for(register int i = first[p];~i;i = pre[i])
        if(!id[to[i]])
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,efa[to[i]] = i,
            dfs(to[i]),
            sz[p] += sz[to[i]];
        else if(id[to[i]] < id[p])
            back[p] |= 1 << dep[to[i]] - 1;
    --top;
}
inline int check(int s,int l,int r)
{
    for(register int i = l;i <= r;++i)
        if(!(s / pw[i - 1] % 3))
            return 0;
    return 1;
}
int main()
{
    freopen("absurdity.in","r",stdin),freopen("absurdity.out","w",stdout);
    memset(first,-1,sizeof first);
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    int u,v;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    pw[0] = 1;
    for(register int i = 1;i <= D;++i)
        pw[i] = 3 * pw[i - 1];
    for(register int u = 1,cur;u <= n;++u)
        if(!fa[u])
        {
            tot = 0,dep[u] = 1,dfs(u);
            memset(f[cur = 0],0x3f,sizeof f[0]),f[0][0] = 0,f[0][2] = a[u];
            for(register int i = 2;i <= tot;++i,cur ^= 1)
            {
                memset(f[cur ^ 1],0x3f,sizeof f[cur ^ 1]);
                for(register int s = 0,t,dir,flag;s < pw[dep[rk[i - 1]]];++s)
                    if(f[cur][s] < 0x3f3f3f3f && check(s,dep[rk[i]],dep[rk[i - 1]]))
                    {
                        t = s % pw[dep[rk[i]] - 1];
                        flag = 0,dir = t;
                        for(register int j = 1;j <= dep[rk[i]];++j)
                            if(back[rk[i]] & (1 << j - 1))
                                t / pw[j - 1] % 3 == 2 && (flag = 1),
                                !(t / pw[j - 1] % 3) && (dir += pw[j - 1]);
                        if(flag)
                            f[cur ^ 1][t + pw[dep[rk[i]] - 1]] = min(f[cur ^ 1][t + pw[dep[rk[i]] - 1]],f[cur][s]);
                        else
                            f[cur ^ 1][t] = min(f[cur ^ 1][t],f[cur][s]);
                        dir += pw[dep[rk[i]] - 1] * 2;
                        f[cur ^ 1][dir] = min(f[cur ^ 1][dir],f[cur][s] + a[rk[i]]);
                    }
            }
            cur = 0x3f3f3f3f;
            for(register int i = 0;i < pw[dep[rk[tot]]];++i)
                if(check(i,1,dep[rk[tot]]))
                    cur = min(cur,f[(tot & 1) ^ 1][i]);
            ans += cur;
        }
    printf("%d\n",ans);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment