wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

二分图匹配

二分图最大权匹配

网络流综合

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最小生成树

最短路

差分约束

2-SAT

基环树

[[ item.c ]]

基环树

## 基环树的表述
![](/media/content_img/unicyclic-01.png)

## ZJOI 2008 骑士
**[ZJOI2008 骑士](https://www.luogu.com.cn/problem/P2607)**
有`n`个人，每个人有一个最讨厌的人（不会是自己）
现在要选一些人，使得一个人和他讨厌的人不会同时被选进来（实际上就是独立集）
每个点有点权，现在要使得点权之和尽量大

**算法分析**
> 每个人，向最讨厌的人连边

那么构成了基环树，$$(p, p')$$，求基环树的**独立集**（相邻的点不能同时被选上）

> 基环树 dp 第一部分，树形 dp

基环树，**环上的每个点都往外挂一些树**，针对这些部分，可以考虑**树形 dp**
根节点在环上，定义$$dp(u, 0/1)$$表示`u`这棵子树，根节点有没有选，能够选出的最大权值和

> 对于环呢？

做一遍环上 dp，可以破环成链，每个点选的代价是$$dp(u, 1)$$，不选的代价是$$dp(u, 0)$$
枚举起点选/不选，跑一遍 dp

> 怎么判断是环上的点还是树上的点？

1）不停地$$v \to p_v$$往前跳，跳到一个已经被访问过的点$$u$$，$$u$$就是一个环上的点
2）找到整个环，从$$u$$开始再跳一遍
```bash
let v = u
let cycle = {}

while true until v == u break
	cycle.push_back(v)
	oncycle[v] = true
	v = p[v]
```

> 树形 dp

```bash
for v in cycle:
	dfs(v) 树形 dp，注意排除环上的点
	基环树进行树形 dp，我们只考虑不在环上的儿子
```

> 环上 dp，用$$f(u, 0/1)$$来求解环上 dp

1）枚举**最开始的点选/不选**，状态用$$tp$$来表示
```bash
for tp = {0, 1} for j = {0, 1}:
    if j == tp, then f(0, j) = dp( cycle[0], j )
	else f(0, j) = -inf
```

2）接着对`for i = 1 to |cycle|, cycle[i]`，考虑环上 dp
```math
\displaystyle
f(i, 0) = \max(f(i-1, 0), f(i-1, 1)) + dp(u, 0) \\
f(i, 1) = f(i-1, 0) + dp(u, 1)
```

3）最后的答案
如果`tp = 0`，最开始的点不选，那么$$ans = \max (f(m-1, 0), f(m-1, 1))$$
否则，$$ans = f(m-1, 0)$$

### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;

vector<int> p(n + 1);
    vector<i64> wgt(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> wgt[i] >> p[i];
    }

vector<vector<int> > g(n + 1);
    for (int i = 1; i <= n; i++) {
        int u = p[i], v = i;
        g[u].emplace_back(v);
    }

// find cycle, vis 记得用时间戳
    vector<int> vis(n + 1), oncyc(n + 1);
    vector<vector<int> > cycles;

for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        // 往前跳，找到环上的点
        int x = i;
        while (!vis[x]) {
            vis[x] = i;
            x = p[x];
        }
        if (vis[x] != i) continue;

// vis[x] == i, 当前有新环，找到整个环
        vector<int> cyc;
        int v = x;
        while (true) {
            cyc.emplace_back(v), oncyc[v] = 1;
            v = p[v];
            if (v == x) break;
        }
        cycles.emplace_back(cyc);
    }

// tree dp
    vector dp(n + 1, vector<i64>(2, 0));

auto dfs = [&](auto &dfs, int u) -> void {
        dp[u][1] = wgt[u];
        for (auto v : g[u]) {
            if (oncyc[v]) continue;
            dfs(dfs, v);

dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0]; 
        }
    };

i64 ans = 0;

auto cycDP = [&](const vector<int> &cyc) -> i64 {
        i64 res = -inf<i64>;
        int m = cyc.size();

for (int tp = 0; tp < 2; tp++) {
            vector f(m, vector<i64>(2, -inf<i64>));

for (int j = 0; j < 2; j++) {
                f[0][j] = (j == tp ? dp[cyc[0]][j] : -inf<i64>);
            }

for (int i = 1; i < cyc.size(); i++) {
                auto u = cyc[i];
                f[i][0] = max(f[i-1][0], f[i-1][1]) + dp[u][0];
                f[i][1] = f[i-1][0] + dp[u][1];
            }

if (tp == 0) chmax(res, max(f[m - 1][0], f[m - 1][1]));
            else chmax(res, f[m - 1][0]);
        }

return res;
    };

for (const auto &cyc : cycles) {
        // tree dp
        for (auto u : cyc) {
            dfs(dfs, u);
        }
        // cycle dp
        ans += cycDP(cyc);
    }
    cout << ans << "\n";
}
```
## Island
**[P4381 [IOI 2008] Island](https://www.luogu.com.cn/problem/P4381)**
每个连通分量是一个基环树，在每个连通分量中找到最长简单路径，然后把它们加起来

**算法分析**
> 树内部求直径

可以用树形 dp，维护当前这个点**往下最深的长度**，然后合并的时候，更新直径

> 环上的点，怎么处理？

之前已经求出了，每个点往下最深的距离是多少，记为$$D_u$$
![](/media/content_img/unicyclic-02.png)
![](/media/content_img/unicyclic-03.png)

**基环树的建图方式**，一般考虑连边$$i \to p_i$$，`g[ p[i] ].emplace_back(i)`

### 算法实现
> 边权的处理，注意基环树所有点的出度是`1`，$$(i \to p_i)$$

涉及到边权的时候，只需要把边权转化成点权，$$w(i, p_i) = w(i)$$
之后涉及到破环成链，对环单独提取，求前缀和的时候
```bash
for i = 0 to |cyc|
	int u = cyc[i]
	S[i + 1] = S[i] + w(u)
```
> 处理读入

```bash
void solve(int cas) {
    int n;
    cin >> n;

using pr = pair<int, i64>;
    vector<vector<pr> > g(n + 1);
    vector<int> p(n + 1);
    vector<i64> wgt(n + 1);

for (int i = 1; i <= n; i++) {
        cin >> p[i] >> wgt[i];
        g[p[i]].emplace_back(i, wgt[i]);
    }
}
```
> 破环成链，单调队列

```bash
void solve() {
    auto cycDP = [&](const vector<int> &cyc) -> i64 {
        auto a = cyc;
        a.insert(a.end(), cyc.begin(), cyc.end());

int m = a.size(), sz = cyc.size();
        vector<i64> S(m), d(m);

for (int i = 0; i < m; i++) {
            auto u = a[i];
            d[i] = dp[u];
        }

for (int i = 0; i + 1 < m; i++) {
            int u = a[i], w = wgt[u];
            S[i+1] = S[i] + w;
        }
        i64 res = 0;
        deque<int> q;

for (int i = 0; i < m; i++) {
            while (q.size() and abs(i - q.front()) >= sz) q.pop_front();
            if (q.size()) chmax(res, d[i] + S[i] + (d[q.front()] - S[q.front()]));
            while (q.size() and d[q.back()] - S[q.back()] <= d[i] - S[i]) q.pop_back();
            q.emplace_back(i);
        }

return res;
    };
	// 计算答案
	i64 ans = 0;
    for (const auto &cyc : cycles) {
        // tree dp
        i64 res = 0;
        for (auto u : cyc) {
            i64 diam = 0;
            dfs(dfs, u, diam);
            chmax(res, diam);
        }

// cycle dp
        auto res2 = cycDP(cyc);
        chmax(res, res2);

ans += res;
    }
    cout << ans << '\n';
}
```
## JOISC 2016 电报
**[P14401 [JOISC 2016] 电报 / Telegraph](https://www.luogu.com.cn/problem/P14401)**
给定`n`个点，每个点的出度都是`1`，给出这`n`个点初始指向的点$$a_i$$
但是你可以花$$c_i$$的代价，改变这个点的指向，求让所有的点**强连通**，所需要的最小花费

**算法分析**
![](/media/content_img/unicyclic-04.png)
![](/media/content_img/unicyclic-05.png)

### 算法实现
```bash
void solve(int cas) {
	// 其他代码省略，只统计代价
    i64 ans = 0;
    for (int u = 1; u <= n; u++) {
        sort(g[u].begin(), g[u].end(), [&](int a, int b) {
            return C[a] < C[b];
        });

int m = g[u].size();
        for (int i = 0; i < m - 1; i++) {
            auto v = g[u][i];
            del[v] = 1, ans += C[v];
        }
    }

for (const auto &cyc : cycles) {
        bool ready = false;

for (auto u : cyc) {
            if (del[u]) {
                ready = true;
                break;
            }
        }
        if (ready) continue;

i64 res = inf<i64>;
        for (auto u : cyc) {
            auto mx = g[u].back();
            i64 now = C[mx];

if (g[u].size() >= 2) {
                int m = g[u].size();
                now -= C[g[u][m - 2]];
            }
            chmin(res, now);
        }
        ans += res;
    }
    cout << ans << "\n";
}
```
## Card Game
**[HDU6403 Card Game](https://acm.hdu.edu.cn/showproblem.php?pid=6403)**
给定`n`张牌，每张牌`2`个数字，正面是$$x$$，反面是$$y$$
可以翻转一些牌（翻转后正面`y`，反面`x`），使得所有牌翻转之后，正面不一样
1）最小翻转步数，2）方案数

**算法分析**
![](/media/content_img/unicyclic-06.png)
![](/media/content_img/unicyclic-07.png)

### 算法实现
```bash
struct Edge {
    int x, y;
    int costx, costy;
};

void solve(int cas) {
    int n;
    cin >> n;
    int N = n * 2;

vector<Edge> edges(N + 1);
    vector<vector<int> > g(N + 1);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;

edges[i] = {x, y, 0, 1};
        g[x].emplace_back(i);
        if (y != x) g[y].emplace_back(i);
    }

// extract components
    vector<int> vis(N + 1), in(N + 1), pa(N + 1);
    vector<vector<int> > SCC;
    using arr = array<int, 3>;
    vector<arr> SCCedges;
    // [bid, ed, st]

for (int i = 1; i <= N; i++) {
        if (!vis[i] and g[i].size() > 0) {
            vector<int> comp;
            int backcnt = 0, ed = -1, st = -1, bid = -1;

auto dfs = [&](auto &dfs, int u, int from) -> void {
                vis[u] = 1;
                comp.emplace_back(u);

for (auto eid : g[u]) {
                    if (eid == from) continue;

int v = edges[eid].x ^ edges[eid].y ^ u;
                    if (vis[v] == 0) {
                        pa[v] = u, in[v] = eid;
                        dfs(dfs, v, eid);
                    } else if (vis[v] == 1) {
                        backcnt++;
                        ed = u, st = v, bid = eid;
                    }
                }

vis[u] = 2;
            };

dfs(dfs, i, -1);
            SCC.emplace_back(comp);

if (backcnt >= 2) {
                cout << "-1 -1\n";
                return;
            }
            SCCedges.emplace_back(arr{bid, ed, st});
        }
    }

vector<int> dp(N + 1), f(N + 1);
    auto treeDP = [&](int cid) -> pair<int, mint> {
        const auto &comp = SCC[cid];
        int rt = comp[0];

auto dfs1 = [&](auto &dfs1, int u, int fa) -> void {
            dp[u] = 0;
            for (auto eid : g[u]) {
                int v = edges[eid].x ^ edges[eid].y ^ u;
                if (v == fa) continue;
                dfs1(dfs1, v, u);

int cost = (edges[eid].x == v ? edges[eid].costx : edges[eid].costy);
                dp[u] += dp[v] + cost;
            }
        };
        dfs1(dfs1, rt, -1);

auto dfs2 = [&](auto &dfs2, int u, int fa) -> void {
            if (fa == -1) f[u] = dp[u];
            for (auto eid : g[u]) {
                int v = edges[eid].x ^ edges[eid].y ^ u;
                if (v == fa) continue;

int cuv = (edges[eid].x == v ? edges[eid].costx : edges[eid].costy);
                int cvu = (edges[eid].x == u ? edges[eid].costx : edges[eid].costy);

f[v] = f[u] - cuv + cvu;
                dfs2(dfs2, v, u);
            }
        };
        dfs2(dfs2, rt, -1);

int mincost = inf<int>;
        for (auto u : comp) chmin(mincost, f[u]);

mint way = 0;
        for (auto u : comp) if (f[u] == mincost) way += 1;

return make_pair(mincost, way);
    };

vector<int> oncyc(N + 1);
    vector<int> D(N + 1);
    auto dfscyc = [&](auto &self, int u, int fa) -> void {
        D[u] = 0;
        for (auto eid : g[u]) {
            int v = edges[eid].x ^ edges[eid].y ^ u;
            if (oncyc[v] or v == fa) continue;

self(self, v, u);
            int cost = (edges[eid].x == v ? edges[eid].costx : edges[eid].costy);
            D[u] += D[v] + cost;
        }
    };

auto pseudotree = [&](int cid) -> pair<int, mint> {
        const auto &[bid, ed, st] = SCCedges[cid];
        assert(bid != -1);

using pr = pair<int, int>;
        vector<pr> cyc;
        int u = ed;
        while (u != st) {
            cyc.emplace_back(u, in[u]), oncyc[u] = 1;
            u = pa[u];
        }
        cyc.emplace_back(st, bid), oncyc[st] = 1;

int base = 0;
        for (auto [u, _] : cyc) {
            dfscyc(dfscyc, u, -1);
            base += D[u];
        }

if (cyc.size() == 1) {
            return make_pair(base, mint(1));
        }

reverse(cyc.begin(), cyc.end());
        int C1 = 0, C2 = 0, sz = cyc.size();

for (int i = 0; i < sz; i++) {
            auto [v, eid] = cyc[i];
            auto [u, _] = cyc[(i - 1 + sz) % sz];

C1 += (edges[eid].x == v ? edges[eid].costx : edges[eid].costy);
            C2 += (edges[eid].x == u ? edges[eid].costx : edges[eid].costy);
        }

if (C1 == C2) {
            return make_pair(base + C1, mint(2));
        }

auto C = min(C1, C2);
        return make_pair(base + C, mint(1));
    };

int ans = 0;
    mint totway = 1;
    for (size_t i = 0; i < SCC.size(); i++) {
        auto [bid, ed, st] = SCCedges[i];
        
        if (bid == -1) {
            auto [mincost, way] = treeDP(i);
            ans += mincost, totway *= way;
        }
        else {
            auto [mincost, way] = pseudotree(i);
            ans += mincost, totway *= way;
        }
    }

cout << ans << " " << totway << "\n";
    return;
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

基环树

目录