跃迁引擎启动

发表于 更新于 分类于 阅读次数：

题意

给定一棵树，每个点有权值 $a_i$，有 $m$ 个监控摄像头，每个摄像头可以监控子树内距离根小于等于 $k_i$ 的点，如果一个点被某个摄像头监控，则其不能被选择，每个摄像头你可以花费 $c_i$ 的代价黑掉，使其失效，求最大收益。

其中 $3 \le n,m \le 3 \cdot 10^5$。

分析

考虑最大权闭合子图建图，每次选上一个点会获得一个价值，但是能够监控到他的摄像头必须全部黑掉，也就是失去一个价值，因此原题等价于求这个图的最大流。

显然不能直接建图来流，但是这个图很特殊，把图反过来看，源点的流量是流向所有的摄像头，摄像头的流量从对应深度的子树内流出到汇点。

考虑 $dp[u][j]$ 表示 $u$ 点的子树内，深度为 $j$ 的点能提供多少流量，显然对于每个摄像头，尽量从深度大的点流出，这肯定是优的。

上面关于深度的信息可以长链剖分或者启发式合并在 $O(n\log n)$ 的时间内维护。

阅读全文 »

发表于 更新于 分类于 阅读次数：

圆方树

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
int cnt;
namespace cactus {
    struct E { 
        int to, nxt; 
    } e[maxn * 2];
    int head[maxn], ecnt;
    void adde(int u, int v) {
        e[++ecnt] = {v, head[u]};
        head[u] = ecnt;
    }
    int tot, dfn[maxn], fa[maxn];
    bool ring[maxn];
    void clear(int n) { 
        cnt = ecnt = tot = 0;
        for (int i = 1; i <= n; i++) {
            head[i] = dfn[i] = ans[i] = 0;
        }
    }
    void dfs(int u, int f) {
        dfn[u] = ++tot;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (v == f) continue;
            if (!dfn[v]) {
                fa[v] = u; ring[u] = false;
                dfs(v, u);
                if (!ring[u]) { 
                    edge[u].push_back(v); edge[v].push_back(u); 
                }
            } else if (dfn[v] < dfn[u]) {
                cnt++; int rt = cnt + n;
                bcc[cnt].clear();
                edge[rt].push_back(v); 
                edge[v].push_back(rt);
                bcc[cnt].push_back(v);
                for (int x = u; x != v; x = fa[x]) {
                    ring[x] = true;
                    bcc[cnt].push_back(x);
                    edge[rt].push_back(x); 
                    edge[x].push_back(rt);
                }
                ring[v] = true;
            }
        }
    }
    void build() {
        dfs(1, 0);
    }
}
阅读全文 »