- 基环树，顾名思义就是基于一个环的树，有n个点和n条边。只有一个环的图，其实并不是树，而是一种特殊的图。
- 基环树分类：
<1>内向树：每个点出度为1；
<2>外向树：每个点入度为1；
<3>无向树：建的是无向边； - 基环树解题的思路：找到环，然后断环成树。
例题：
- 洛谷p2607 骑士
<1>题目大意：有n个骑士，每个骑士的战斗力为w，每个骑士都有一个讨厌的骑士，现在要选一些骑士出征打仗，问最大能选择的战斗力为多少。若a讨厌b，那么a和b不能一起出征。
<2>思路分析：这题目是不是有点像《没有上司的舞会》？那么就做类似的思考，因为如果这是一棵树的话就好办了，可是题目给的是个图，还是有环的图。我们发现这是一颗基环树，所以找到环的两端的l和r点然后断开就可以了。然后分别对以l和r为根的子树进行dp取两者的最大值就可以了。那么是不是可能会有疑问：为什么这样两者取最大值就包含了全部情况了呢？因为分别以l和r做根就是不考虑l和不考虑r的情况，而两者取最大值就相当于是包含了全集。至于为什么要找这个l和r，因为我们要断环成树啊，不然每个骑士都出不去。
<3>代码：写的时候注意要开longlong，wa了好几发了；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
typedef long long ll;
const int inf = 0x3f3f3f3f;
ll w[N],vis[N];
vector<ll> a[N];
ll l,r;
ll dp[N][2];
void find(ll u,ll fa) {
vis[u] = 1;
for(auto i : a[u]) {
if(i == fa) {
l = u;
r = fa;
return;
}
if(vis[i]) continue;
find(i,fa);
}
}
ll dfs(ll u,ll root) {
dp[u][1] = w[u],dp[u][0] = 0;
for(auto v : a[u]) {
if(v == root) continue;
dfs(v,root);
dp[u][0] += max(dp[v][1],dp[v][0]);
dp[u][1] += dp[v][0];
}
return dp[u][0];
}
void solved() {
int n;
cin >> n;
ll ans = 0;
for(int i = 1; i <= n; i++) {
int u;
cin >> w[i] >> u;
a[u].push_back(i);
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
l = r = 0;
find(i,i);
if(r) {
ll sum1 = dfs(l,l);
ll sum2 = dfs(r,r);
ans += max(sum1,sum2);
}
}
}
cout << ans << "\n";
}
int main() {
int t = 1;
//cin >> t;
while(t--) {
solved();
}
return 0;
}
- CFS1867D Cyclic Operations
<1>题目大意：
Egor 有一个长度为 \(n\) 的数组 \(a\) ，最初由零组成。然而，他想把它变成另一个长度为 \(n\) 的数组 \(b\) 。
由于埃戈尔不走简单的路径，所以只能使用下面的操作（可能是零次，也可能是多次）：
-
选择长度为 \(k\) 的数组 \(l\) ( \(1 \leq l_i \leq n\) ，所有 \(l_i\) 都是不同的)，并将每个元素 \(a_{l_i}\) 改为 \(l_{(i\%k)+1}\) 。( \(1 \leq i \leq k\) ).
他开始关注是否可以只通过这些操作得到数组 \(b\) 。由于 Egor 还是个程序员初学者，他请求您帮助他解决这个问题。
操作 \(\%\) 意味着取余数，也就是说， \(a\%b\) 等于数字 \(a\) 除以数字 \(b\) 的余数。<2>思路分析：我们发现，如果某个位置的值和它的下标不一样，假设下标是a，值是b。那么我们一定可以构造类似[a,b......]的l数组去改变a位置的值，所以我们可以压根不用管b位置变成什么样，也就是说，a变成什么样是和b有关的，所以考虑构造一个有向图，边由a指向b。所以，不在环上的点，怎么构造都行，但是在环上的点就需要等于环长度的数组来构造了。所以环的长度必须为k。还有就是特判一下k为1的时候，下标必须等于值的大小，否则若是下标等于值的大小但是k不为1是构造不出来的。
<3>PS：重新写的时候还是出了点小问题，本来想着用拓扑排序把除了环以外点先去了，然后后来我也不知道为什么自己否定自己了。。。可能没想清楚吧。然后就是这可能是一颗基环树森林，所以不能只考虑一个根，重写的时候给我wa麻了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int a[N],vis[N];
vector<int> g[N];
int res;
void dfs(int u,int fa) {
vis[u] = 1;
res++;
for(auto v : g[u]) {
if(v == fa) return;
if(vis[v]) continue;
dfs(v,fa);
}
}
void solved() {
int n,k;
cin >> n >> k;
bool flag = 1;
vector<int> d(n + 1);
for(int i = 1; i <= n; i++) {
vis[i] = 0;
g[i].clear();
cin >> a[i];
g[i].push_back(a[i]);
d[a[i]]++;
}
if(k == 1) {
for(int i = 1; i <= n; i++) {
if(a[i] != i) flag = 0;
}
if(flag) cout << "YES\n";
else cout << "NO\n";
return;
} else {
for(int i = 1; i <= n; i++) {
if(a[i] == i) flag = 0;
}
if(!flag) {
cout << "NO\n";
return;
}
}
queue<int> q;
for(int i = 1; i <= n; i++) {
if(!d[i]) q.push(i);
}
while(!q.empty()) {
auto t = q.front();q.pop();
vis[t] = 1;
if(--d[g[t][0]] == 0) q.push(g[t][0]);
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
res = 0;
dfs(i,i);
if(res != k) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
int main() {
int t = 1;
cin >> t;
while(t--) {
solved();
}
return 0;
}