目录
算法解析
基环树与基环森林
基环树是指 有且仅有 一个环的树。基环森林是指若干棵基环树构成的森林。
对于有向图,基环树可分为 内向基环树 和 外向基环树:
- 内向基环树:所有点 有且只有 一条出边
- 外向基环树:所有点 有且只有 一条入边
基环树和基环森林都有 点数等于边数 的特点。
基环森林由若干基环树组成,因此下面只讲解如何解决基环树上的问题。
核心思路:
- 将环找出来看作树根
- 不在环上的点只属于一个环上点的子树。对每个环上点的子树分别 \(dp\) 或 \(dfs\) 遍历统计信息
- 破环成链,每个环上点代表它子树的信息。在链上 \(dp\)。有时可使用 单调队列 优化。这一步可看作将割裂的部分合并。
模板
void get_loop(int x, int fa) { // 找基环树上的环
dfn[x] = ++ rk;
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v; LL w = E[i].w;
if(v == fa) continue;
if(dfn[v]) {
if(dfn[v] < dfn[x]) continue;
else {
loop[++ cnt] = v; // loop 存环上点的编号
preE[v] = i; // preE 存环上点之间的连边
for(; v != x; v = E[faE[v] ^ 1].v) {
loop[++ cnt] = E[faE[v] ^ 1].v;
preE[loop[cnt]] = faE[v];
}
}
}
else {
faE[v] = i;
get_loop(v, x);
}
}
}
void DP(int x, int fa) { // 以基环树的环上的点为根,不经过环上其它的点,统计它的子树内的某些最优值
do sth...
}
for(int i = 1; i <= n; i ++ ) {
cnt = 0;
if(!dfn[i]) {
get_loop(i, 0); // 找i所在基环树的环
for(int j = 1; j <= cnt; j ++ ) vis[loop[j]] = 1;
for(int j = 1; j <= cnt; j ++ ) DP(loop[j], 0); // 可以是dp,也可以是其他操作
for(int j = 1; j <= cnt * 2; j ++ ) { // 破环成链,算环上各点之间的边权
if(j > cnt) loop[j] = loop[j - cnt];
if(j == 1) {S[j] = 0; continue;}
else S[j] = S[j - 1] + W[preE[loop[j]]];
}
LL maxn = 0;
int l = 1, r = 0;
for(int j = 1; j <= cnt * 2; j ++ ) { // 单调队列求解答案
while(l <= r && j - q[l] + 1 > cnt) l ++;
if(l <= r) {
do sth...
}
while(l <= r && ...) r --;
q[++ r] = j;
}
res += ...; // 统计答案
}
}
例题
[NOIP2018 提高组] 旅行
[题目
题意:
- 给你一张 \(n\) 个点, \(m\) 条边的图。可任选一个点作为起点,每次可去一个没有去过的点 或 上一个到当前点的点。当到一个之前没到过的点时将该点的编号记录下来。求最小的编号序列。
- \(1 \leq n \leq 5000\), \(m = n - 1\) 或 \(n\)
分析:
如果 \(m = n - 1\),那么是简单的。我们以 \(1\) 为起点,每次往编号最小的儿子的子树里递归。刚进入某个点时记下编号。
如果 \(m = n\),发现这是一棵 基环树。考虑对于任意一种遍历方式,我们将经过的边标记。那么所有标记的边与所有点 一定构成一棵树。也就是说 环上会有一条边不被经过。那么把环找出来,枚举不被经过的边打上标记,然后按照树的方式得到一个答案,将所有答案取最优即可。
时间复杂度 \(O(n^2)\)
CODE:
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair< int, int > PII;
const int N = 5010;
int dfn[N], rk;
int n, m, faE[N], fat[N], head[N];
int idx[N], tot, ans[N], res[N], h, k, r;
vector< PII > G[N];
struct EE {
int u, v, id;
}ET[N * 2];
struct edge {
int v, last, id;
}E[N * 2];
void add(int u, int v, int ide) {
E[++ tot].v = v;
E[tot].last = head[u];
E[tot].id = ide;
head[u] = tot;
}
void dfs(int x, int fa) {
fat[x] = fa; dfn[x] = ++ rk;
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v, ide = E[i].id;
if(v == fa) continue;
if(dfn[v]) {
if(dfn[v] < dfn[x]) continue;
idx[++ k] = ide;
for(; v != x; v = fat[v]) {
idx[++ k] = faE[v];
}
}
else faE[v] = ide, dfs(v, x);
}
}
void dfs0(int x, int fa, int ID) {
res[++ h] = x;
for(auto v : G[x]) {
if(v.first == fa || v.second == ID) continue;
dfs0(v.first, x, ID);
}
}
void solve(int ID) {
h = 0;
dfs0(1, 0, ID);
bool flag = 0;
for(int i = 1; i <= n; i ++ ) {
if(res[i] < ans[i]) {
flag = 1;
break;
}
else if(res[i] > ans[i]) {
flag = 0;
break;
}
}
if(flag) {
for(int i = 1; i <= n; i ++ ) ans[i] = res[i];
}
}
bool cmp(EE x, EE y) {
return x.v < y.v;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) ans[i] = n;
for(int i = 1; i <= m; i ++ ) {
int U, V;
scanf("%d%d", &U, &V);
ET[++ r] = (EE) {U, V, i};
ET[++ r] = (EE) {V, U, i};
}
if(m == n - 1) {
for(int i = 1; i <= m * 2; i ++ ) {
G[ET[i].u].pb(make_pair(ET[i].v, ET[i].id));
}
for(int i = 1; i <= n; i ++ ) sort(G[i].begin(), G[i].end());
solve(0);
}
else {
for(int i = 1; i <= m * 2; i += 2) {
add(ET[i].u, ET[i].v, ET[i].id);
add(ET[i + 1].u, ET[i + 1].v, ET[i].id);
}
dfs(1, 0);
for(int i = 1; i <= m * 2; i ++ ) {
G[ET[i].u].pb(make_pair(ET[i].v, ET[i].id));
}
for(int i = 1; i <= n; i ++ ) sort(G[i].begin(), G[i].end());
for(int i = 1; i <= k; i ++ ) {
solve(idx[i]);
}
}
for(int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
[ZJOI2008]骑士
题意:
- 给你一个 \(n\) 个点的基环森林,点有点权。求基环森林的 最大点独立集
- \(1 \leq n \leq 10^6,1 \leq w_i \leq 10^6\)
分析:
树上的最大点独立集是简单的:设 \(dp_{i, 0/1}\) 表示以 \(i\) 为根的子树中, \(i\) 号点不选/选 的最大点独立集。转移不再叙述。
考虑放在基环树上该怎么做:首先把环找出来。对于环上的点,可以求出以它为根的子树的最大点独立集。这里的子树不包括环上的点。 然后将环断开\(dp\)。设 \(f_{i, 0/1, 0/1}\) 表示链上前 \(i\) 个点考虑了它们各自的子树,第 \(i\) 个点不选/选,第一个点不选/选 的最大点独立集。那么有转移:
-
\(i \ne n\)
\(f_{i, 0, 0} = max(f_{i - 1, 0, 0}, f_{i - 1, 1, 0}) + dp_{i, 0}\)
\(f_{i, 0, 1} = max(f_{i - 1, 0, 1}, f_{i - 1, 1, 1}) + dp_{i, 0}\)
\(f_{i, 1, 0} = f_{i - 1, 0, 0} + dp_{i, 1}\)
\(f_{i, 1, 1} = f_{i - 1, 0, 1} + dp_{i, 1}\) -
\(i = n\)
\(f_{i, 0, 0} = max(f_{i - 1, 0, 0}, f_{i - 1, 1, 0}) + dp_{i, 0}\)
\(f_{i, 0, 1} = max(f_{i - 1, 0, 1}, f_{i - 1, 1, 1}) + dp_{i, 0}\)
\(f_{i, 1, 0} = f_{i - 1, 0, 0} + dp_{i, 1}\)
初始值为 \(f_{1, 0, 0} = dp_{1, 0},f_{1, 1, 1} = dp_{1, 1}\)
时间复杂度 \(O(n)\)
CODE:
#include<bits/stdc++.h> // 基环森林上独立集
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL INF = 1e16;
inline int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
return x * f;
}
bool vis[N];
int n, hate[N], loop[N], dfn[N], rk, cnt, tot, head[N], fat[N];
LL dp[N][2], attack[N], f[N][2][2], res;
struct edge {
int v, last;
}E[N * 2];
void add(int u, int v) {
E[++ tot].v = v;
E[tot].last = head[u];
head[u] = tot;
}
void dfs(int x, int fa) {
dfn[x] = ++ rk; fat[x] = fa;
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v;
if(v == fa) continue;
if(dfn[v]) {
if(dfn[v] < dfn[x]) continue;
loop[++ cnt] = v;
for(; v != x; v = fat[v]) {
loop[++ cnt] = fat[v];
}
}
else dfs(v, x);
}
}
void DP(int x, int fa) {
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v;
if(v == fa || vis[v]) continue;
DP(v, x);
dp[x][0] += max(dp[v][0], dp[v][1]);
dp[x][1] += dp[v][0];
}
dp[x][1] += attack[x];
}
int main() {
n = read();
for(int i = 1; i <= n; i ++ ) {
attack[i] = 1LL * read(); hate[i] = read();
add(i, hate[i]);
add(hate[i], i);
}
for(int i = 1; i <= n; i ++ ) {
if(!dfn[i]) {
cnt = 0;
dfs(i, 0);
for(int j = 1; j <= cnt; j ++ ) vis[loop[j]] = 1;
for(int j = 1; j <= cnt; j ++ ) DP(loop[j], 0);
for(int j = 1; j <= cnt; j ++ ) f[j][0][0] = f[j][0][1] = f[j][1][0] = f[j][1][1] = -INF;
f[1][0][0] = dp[loop[1]][0]; f[1][1][1] = dp[loop[1]][1]; // 选
for(int j = 2; j <= cnt; j ++ ) {
if(j != cnt) {
f[j][0][0] = max(f[j - 1][0][0], f[j - 1][1][0]) + dp[loop[j]][0];
f[j][1][0] = f[j - 1][0][0] + dp[loop[j]][1];
f[j][0][1] = max(f[j - 1][0][1], f[j - 1][1][1]) + dp[loop[j]][0];
f[j][1][1] = f[j - 1][0][1] + dp[loop[j]][1];
}
else {
f[j][0][0] = max(f[j - 1][0][0], f[j - 1][1][0]) + dp[loop[j]][0];
f[j][1][0] = f[j - 1][0][0] + dp[loop[j]][1];
f[j][0][1] = max(f[j - 1][0][1], f[j - 1][1][1]) + dp[loop[j]][0];
}
}
res += max({f[cnt][0][0], f[cnt][1][0], f[cnt][0][1]});
}
}
cout << res << endl;
return 0;
}
[IOI2008] Island
题意:
- 给你一个 \(n\) 个点的基环森林,边有边权。求每棵基环树的直径之和。
- \(1 \leq n \leq 10^6,1 \leq w_i \leq 10^8\)
分析:
还是按照套路,将每棵基环树的环找出来。然后求出 环上点的子树中的直径以及最长链。接下来求跨越两棵子树的最长链。破环成链并复制一倍接在后面,考虑固定一个起点的环可以由一个长度和环相等的区间表示。那么区间里两个元素的答案就是 \(f_x + f_y + dis_{x, y}\)。 \(f_x\) 表示 \(x\) 子树中的最长链。\(dis_{i, j}\) 表示区间中 \(i\) 与 \(j\) 的距离。这个式子可以改写成 \(f_x + f_y + d_y - d_x\)。然后对于一个 \(y\),会用到区间里 \(f_x - d_x\) 最大的 \(x\)。写一个 单调队列 优化即可。
时间复杂度 \(O(n)\)
CODE:
#include<bits/stdc++.h> // 求基环森林中所有基环树的直径之和
using namespace std; // 使用 dfs 序找环
const int N = 1e6 + 10;
typedef long long LL;
int n, u, v, head[N], tot;
int preE[N], dfn[N], rk, cnt, loop[N * 2], faE[N];
LL w, S[N * 2], W[N * 2], res, Maxx, f[N];
int q[N * 2];
bool vis[N];
struct edge {
int v, last; LL w;
}E[N * 2];
void add(int u, int v, LL w) {
E[++ tot].v = v;
E[tot].w = w;
E[tot].last = head[u];
head[u] = tot;
W[tot] = w;
}
void get_loop(int x, int fa) {
dfn[x] = ++ rk;
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v; LL w = E[i].w;
if(v == fa) continue;
if(dfn[v]) {
if(dfn[v] < dfn[x]) continue;
else {
loop[++ cnt] = v;
preE[v] = i;
for(; v != x; v = E[faE[v] ^ 1].v) {
loop[++ cnt] = E[faE[v] ^ 1].v;
preE[loop[cnt]] = faE[v];
}
}
}
else {
faE[v] = i;
get_loop(v, x);
}
}
}
void DP(int x, int fa) {
for(int i = head[x]; i; i = E[i].last) {
int v = E[i].v; LL w = E[i].w;
if(vis[v] || v == fa) continue;
DP(v, x);
Maxx = max(Maxx, f[x] + f[v] + w);
f[x] = max(f[x], f[v] + w);
Maxx = max(Maxx, f[x]);
}
}
int main() {
tot = 1;
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) {
scanf("%d%lld", &v, &w);
add(i, v, w); add(v, i, w);
}
for(int i = 1; i <= n; i ++ ) {
cnt = 0;
if(!dfn[i]) {
Maxx = 0;
get_loop(i, 0); // 找i所在基环树的环
for(int j = 1; j <= cnt; j ++ ) vis[loop[j]] = 1;
for(int j = 1; j <= cnt; j ++ ) DP(loop[j], 0);
for(int j = 1; j <= cnt * 2; j ++ ) {
if(j > cnt) loop[j] = loop[j - cnt];
if(j == 1) {S[j] = 0; continue;}
else S[j] = S[j - 1] + W[preE[loop[j]]];
}
LL maxn = 0;
int l = 1, r = 0;
for(int j = 1; j <= cnt * 2; j ++ ) {
while(l <= r && j - q[l] + 1 > cnt) l ++;
if(l <= r) {
int idx = q[l];
maxn = max(maxn, f[loop[idx]] + f[loop[j]] + S[j] - S[idx]);
}
while(l <= r && f[loop[j]] - S[j] >= f[loop[q[r]]] - S[q[r]]) r --;
q[++ r] = j;
}
res += max(maxn, Maxx);
}
}
cout << res << endl;
return 0;
}
Long Way to be Non-decreasing
题意:
给你一个长为 \(n\) 的数列 \(a_1,....,a_n\) 和一个长为 \(m\) 的数列 \(b_1,...,b_m\),保证 \(1 \leq a_i,b_i \leq m\)。定义一次操作如下:
- 选定一个下标集合 \(S\)。
- 对于 \(\forall i \in S\), \(a_i \gets b_{a_i}\)
问至少多少次操作能使序列 \(a\) 单调不降,输出最小的操作次数。若无法使 \(a\) 单调不降,输出 \(-1\)。
- \(1 \leq n \leq 10^6,1 \leq m \leq 10^6\),\(1 \leq a_i, b_i \leq m\)
分析:
对于每个数 \(x\),将它和 \(b_x\) 连边。那么最后会形成一个 内向基环森林。每个数 \(x\) 可以在一次操作跳到它的后继上。那么问题变成了每个位置 \(i\) 开始在一个节点上,可以花费 \(1\) 代价使它跳到后继点上。问使每个位置上的数单调不降 每个位置所需代价最大值的最小 是多少。
考虑二分答案。那么对于一个 \(mid\),我们可以求出每个位置的数字能够在不超过 \(mid\) 步变成那些数。用数据结构维护,每个位置变成 大于上一个数的最小数,如果到第 \(n\) 个位置都可以选择,那么返回 \(true\),否则返回 \(false\)。理论复杂度 \(O(n \times log_2^2n)\)。
我们考虑从前往后数字是 单调不降 的。因此可以从 \(1\) 枚举 到 \(m\),并判断对于当前位置数字 \(i\) 是否可以在 \(mid\) 步到达。如果不行,让 \(i\) 加 \(1\)。否则判断下一个位置。
下面只需判断一个数字 \(x\) 能否在 \(mid\) 步跳到 \(y\) 上。这个是简单的:如果不位于同一棵基环树,那么显然不可能。如果 \(x\) 和 \(y\) 在同一个环上点的子树中且 \(x\) 在 \(y\) 子树中。那么可以用深度来求出距离。否则如果 \(y\) 是环上点,可以先让 \(x\) 跳到环上,再在环上找出距离。其余情况都不可能。
最后如果每个位置上的数能变成一个合法的数,那么返回 \(true\),否则返回 \(false\)。
时间复杂度 \(O(m \times log_2m)\)
CODE:
#include<bits/stdc++.h> // 内向基环森林
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
int T, n, m, a[N], b[N], to[N], fat[N];
int dep[N], dfn[N], rk, bel[N], lp[N], pos[N], tot;
int Dfn[N], L[N], R[N], o;
vector< int > loop[N];
bool vis[N];
vector< int > E[N];
void dfs(int x, int fa) {
dfn[x] = ++ rk; fat[x] = fa;
for(auto v : E[x]) {
if(v == fa) continue;
if(dfn[v]) {
if(dfn[v] < dfn[x]) continue;
loop[tot].pb(v);
for(; v != x; v = fat[v]) loop[tot].pb(fat[v]);
}
else dfs(v, x);
}
}
void get(int x, int fa, int Top) {
bel[x] = Top; dep[x] = dep[fa] + 1;
Dfn[x] = ++ o; L[x] = o;
for(auto v : E[x]) {
if(v == fa || vis[v]) continue;
get(v, x, Top);
}
R[x] = o;
}
bool check(int lenth) {
int now = 1;
for(int i = 1; i <= m;) {
if(now <= n) {
bool f = 0;
int val = -1;
int x = a[now];
if(lp[bel[x]] != lp[bel[i]]) {
i ++; continue;
}
if(bel[x] == bel[i]) { // 同一个子树
if(Dfn[x] >= L[i] && Dfn[x] <= R[i]) {
if(dep[x] - dep[i] <= lenth) f = 1, val = i;
}
}
else if(bel[i] == i) { // 环上
int c = dep[x] - 1, sz = loop[lp[i]].size();
int p1 = pos[i], p2 = pos[bel[x]];
if(p2 <= p1) c += (p1 - p2);
else c += (sz - p2 + p1);
if(c <= lenth) f = 1, val = i;
}
if(f) now ++;
else i ++;
if(now > n || i > m) break;
}
}
if(now > n) return 1;
return 0;
}
void solve() {
scanf("%d%d", &n, &m);
rk = 0, tot = 0;
for(int i = 1; i <= m; i ++ ) {
dfn[i] = 0;
vis[i] = 0;
vector< int > tmp; swap(tmp, E[i]);
vector< int > g; swap(g, loop[i]);
lp[i] = 0;
}
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for(int i = 1; i <= m; i ++ ) scanf("%d", &b[i]);
for(int i = 1; i <= m; i ++ ) {
to[i] = b[i];
if(i != b[i]) {
E[i].pb(b[i]);
E[b[i]].pb(i);
}
else E[i].pb(b[i]);
}
for(int i = 1; i <= m; i ++ ) {
if(!dfn[i]) {
tot ++;
dfs(i, 0);
if(to[loop[tot][0]] != loop[tot][1]) reverse(loop[tot].begin(), loop[tot].end());
for(int j = 0; j < loop[tot].size(); j ++ ) pos[loop[tot][j]] = j;
for(int j = 0; j < loop[tot].size(); j ++ ) vis[loop[tot][j]] = 1;
for(int j = 0; j < loop[tot].size(); j ++ ) {
o = 0;
get(loop[tot][j], 0, loop[tot][j]);
lp[loop[tot][j]] = tot;
}
}
}
int l = 0, r = m + 10, mid, res = -1;
while(l <= r) {
mid = (l + r >> 1);
if(check(mid)) res = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", res);
}
int main() {
scanf("%d", &T);
while(T -- ) {
solve();
}
return 0;
}
/*
1
10 10
2 8 5 4 8 4 1 5 10 10
6 7 2 6 3 4 1 1 3 5
*/
标签:leq,int,笔记,----,基环树,fa,dfn,loop
From: https://www.cnblogs.com/czlczl/p/18391265