仙人掌(圆方树)"/>
20200804 专题:仙人掌(圆方树)
总览:
无向仙人掌图的定义:
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
处理方法:
建立圆方树
圆方树的建点:
- 原图中的点都是圆点
- 对于每个点双连通分量,新建一个方点,这个方点和环上其它圆点连成菊花图
- 对于不在环上的两个圆点,保留原图中的边
根据仙人掌的性质,易证不存在相邻的两个方点
边 ( u , v ) (u,v) (u,v) 权值的确定:
- 若 u , v u,v u,v 都是圆点,则权值为原图中边权
- 若 u u u 为方点,则权值为 v v v 到 u u u 父亲的最短路
感性理解:
对于图中每一个环建一个方点,环上的圆点与之连边
环与环间的边保持不变
方点与圆点间的边权为圆点到环的出边的距离
性质:
树上圆点的信息对应原图上的信息
树上方点的信息对应环上的信息
建树模板:
inline void build(int fa, int x, int len) {top = dep[x] - dep[fa] + 1;for (int i = x; i != fa; i = f[i]) st[top--] = i, len += dis[i] - dis[f[i]];st[top] = fa;top = dep[x] - dep[fa] + 1;SQT::cnt++;SQT::sum[SQT::cnt] = len;int now = 0;for (int i = 1; i <= top; i++) {int w = min(len - now, now);SQT::edge(SQT::cnt, st[i], w), SQT::edge(st[i], SQT::cnt, w);SQT::be[st[i]] = (w == now);now += dis[st[i + 1]] - dis[st[i]];}return;
}//方点-圆点
inline void tarjan(int fa, int x) {dfn[x] = low[x] = ++tot, dep[x] = dep[fa] + 1, f[x] = fa;for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w;if (z == fa) continue;if (!dfn[z]) {dis[z] = dis[x] + w;tarjan(x, z);low[x] = min(low[x], low[z]);} elselow[x] = min(low[x], dfn[z]);if (dfn[x] < low[z]) SQT::edge(x, z, w), SQT::edge(z, x, w);//圆点-圆点}for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w;if (z == fa) continue;if (f[z] != x && dfn[x] < dfn[z]) build(x, z, w);//取出环,建方点}return;
}//建树
T1 P4244 [SHOI2008]仙人掌图 II
思路:
找仙人掌直径模板
建树后 树形dp 即可
方点的儿子成环,不能直接转移,要先 环形dp 找出环上最短路
环形dp 可以拆环成链,复制一倍
代码:
#include <bits/stdc++.h>
using namespace std;
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define ch() \(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) \? EOF \: *p1++)
inline int in() {int s = 0, f = 1;char x = getchar();while (x < '0' || x > '9') {x = getchar();if (x == '-'
更多推荐
20200804 专题:仙人掌(圆方树)
发布评论