• 基环树(环套树) 总结

    基环树，也是环套树，是一种有 n 个点 n 条边的图，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。

    基环内向树：每个点出度为1（因此每个环上点的子树，儿子指向父亲）

    基环外向树：每个点入度为1（因此每个环上点的子树，父亲指向儿子）

    基环树的关键就是找到环，可以先把环当作这个无根树的 “根” ，也就是把环当成一个点（先不管它），这样一颗基环树就变成了一个普通的树，然后我们先按照解决普通树的方法对“根”的所有子树依次处理求解答案，最后在单独对环上所有的点进行操作求解最终答案即可。

    有向图找环

    1. inline void find(int u,int rt){
    2. 	vis[u] = 1;
    3. 	for(re int i(head[u]) ; i ; i=e[i].nxt){
    4. 		int v = e[i].to;
    5. 		if(v == rt) { r1=u; r2=v; return; } //找到了环，设为这条边的两个端点
    6. 		if(vis[v]) continue;
    7. 		find(v,rt);
    8. 	}
    9. }

    无向图找环

    1. inline void find(int u,int rt){
    2.     vis[u] = 1;
    3.     for(re int i(head[u]) ; i ; i=e[i].nxt){
    4.         int v = e[i].to;
    5.         if(v == rt) continue;
    6.         if(vis[v]){
    7.             fl = 1;
    8.             r1 = u;
    9.             r2 = v;
    10.             return;
    11.         }
    12.         find(v,u);
    13.         if(fl) return;
    14.     }
    15. }

    来看例题

    洛谷 P2607 [ZJOI2008] 骑士

    这道题可以算是一个例题吧，考虑如何进行连边。由于一个人可能被多个人痛恨，那么把一个人痛恨的人作为这个人的父亲节点进行连边。这样这个图就变成了一个有向的基环树。我们每一次找环，把环断开成链，设断开的边的两个端点是 u 和 v，分别对 u 进行 dfs 和 v 进行 dfs，取两个的最大值。由于相邻的两个点最多只能选其中一个，那么这道题断开环之后就变成了一个基础的树形DP。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define re register
    7. #define int long long
    8. #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
    9. #define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
    10. using namespace std;
    11. inline int read(){
    12. 	int x=0,f=1;char ch=getchar();
    13. 	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    14. 	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    15. 	return x*f;
    16. }
    17. const int M = 2e6+10;
    18. int n;
    19. int head[M],w[M],vis[M],f[M][2];
    20. int cnt,sum,res1,res2,r1,r2;
    21. struct edge{
    22. 	int to,nxt;
    23. }e[M];
    24. inline void add(int u,int v){
    25. 	e[++cnt].to = v;
    26. 	e[cnt].nxt = head[u];
    27. 	head[u] = cnt;
    28. }
    29. inline void find(int u,int rt){ //找环
    30. 	vis[u] = 1;
    31. 	for(re int i(head[u]) ; i ; i=e[i].nxt){
    32. 		int v = e[i].to;
    33. 		if(v == rt) { r1=u; r2=v; return; }
    34. 		if(vis[v]) continue;
    35. 		find(v,rt);
    36. 	}
    37. }
    38. inline int dfs(int u,int rt){
    39. 	f[u][0] = 0,f[u][1] = w[u]; //f[u][0]表示不选该节点，f[u][1]表示选
    40. 	for(re int i(head[u]) ; i ; i=e[i].nxt){
    41. 		int v = e[i].to;
    42. 		if(v == rt) continue;
    43. 		dfs(v,rt);
    44. 		f[u][0] += max(f[v][0],f[v][1]); //不选这个点，从它子节点转移过来
    45. 		f[u][1] += f[v][0]; //选这个点就不能选它的子节点
    46. 	}
    47. 	return f[u][0]; //让这个点强制不选
    48. }
    49. signed main(){
    50. 	n=read();
    51. 	rep(i,1,n){
    52. 		w[i]=read();
    53. 		int u=read();
    54. 		add(u,i);
    55. 	}
    56. 	rep(i,1,n){
    57. 		if(!vis[i]){
    58. 			r1 = r2 = 0;
    59. 			find(i,i);
    60. 			if(r1){ //找到了环
    61. 				res1 = dfs(r1,r1);
    62. 				res2 = dfs(r2,r2);
    63. 				sum += max(res1,res2);
    64. 			}
    65. 		}
    66. 	}
    67. 	printf("%lld\n",sum);
    68. 	return 0;
    69. }

    洛谷 P5022 [NOIP2018 提高组] 旅行

    这道题如果没有环的话，就把每一个点的出边按字典序从小到大进行排序，然后每一个点先 dfs 它孩子字典序小的点，最后输出答案即可。

    然后考虑有环的情况。还是跟基环树的题做法一样，找到环，断开，对断边的两个点分别进行 dfs，求出每一种情况的更优解。

    要注意的是，由于这道题要排序，普通的链式前向星实现起来比较困难，用 vector 比较好实现。而且在 dfs 的过程中，我们需要记录走到该点会不会让答案更优。如果会变差，直接 return 就行，变优的话记录下来，接着往下搜索。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #define re register
    8. #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
    9. #define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
    10. using namespace std;
    11. inline int read(){
    12. 	int x=0,f=1;char ch=getchar();
    13. 	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    14. 	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    15. 	return x*f;
    16. }
    17. typedef pair<int,int> pii;
    18. const int M = 1e5+10;
    19. vector<int> g[M];
    20. pii edge[M];
    21. int path[M],vis[M];
    22. int cnt;
    23. int n,m,better,nu,nv;
    24. inline bool dfs(int u){
    25. 	if(!better){
    26. 		if(u > path[cnt]) return 1;
    27. 		if(u < path[cnt]) better = -1;
    28. 	}
    29. 	path[cnt++] = u;
    30. 	vis[u] = 1;
    31. 	for(auto v : g[u]){
    32. 		if(vis[v]) continue;
    33. 		if(v==nu && u==nv) continue;
    34. 		if(v==nv && u==nu) continue;
    35. 		if(dfs(v)) return 1;
    36. 	}
    37. 	return 0;
    38. }
    39. signed main(){
    40. 	n=read(),m=read();
    41. 	rep(i,1,m){
    42. 		int u=read(),v=read();
    43. 		edge[i].first = u,edge[i].second = v;
    44. 		g[u].push_back(v);
    45. 		g[v].push_back(u);
    46. 	}
    47. 	memset(path,0x3f,sizeof(path));
    48. 	rep(i,1,n) sort(g[i].begin(),g[i].end());
    49. 	if(m == n-1) dfs(1);
    50. 	else{
    51. 		rep(i,1,m){
    52. 			nu = edge[i].first;
    53. 			nv = edge[i].second;
    54. 			memset(vis,0,sizeof(vis));
    55. 			cnt = better = 0;
    56. 			dfs(1);
    57. 		}
    58. 	}
    59. 	rep(i,0,n-1) printf("%d ",path[i]);
    60. 	return 0;
    61. }

    洛谷 P1399 [NOI2013] 快餐店

    这道题个人认为可以算是比较难的题了。

    首先这是一道基环树的题。给定 n 个点和 n 条边，而且保证联通，那么就存在一个环。

    要求出一个点到离它距离最远的点的距离最小，显然跟直径有关，求出此基环树的直径，答案为直径除以 2。

    那么考虑如何求直径。有两种情况。

    1.直径不经过基环。

    2.直径经过基环。

    在求直径之前，我们需要将哪些点在环上记录下来。我们从 1 号点开始深搜找环。具体看代码注释。

    1. inline bool find(int u){
    2.     vis[u] = 1; //这个点记录为走过 
    3.     for(re int i(head[u]) ; i ; i=e[i].nxt){
    4.         int v = e[i].to;
    5.         if(v == fa[u]) continue; //走到了父亲不行 
    6.         fa[v] = u;
    7.         w[v] = e[i].w; //将这条边的边权转化为儿子的点权，和树剖的转化类似 
    8.         if(!vis[v]) { if(find(v)) return 1; } //如果这个点没有走过而且后面能找到环，就一直往回return 
    9.         else{ //找到了环 
    10.             int p = u; //枚举环上的点 
    11.             while(1){
    12.                 inc[p] = 1; //inc[p]=1表示p在环上 
    13.                 cv[++tot] = p; //环上的点的编号，由于后面操作，我们需要重新编号 
    14.                 cw[tot] = w[p]; //环上这个编号点的点权 
    15.                 p = fa[p]; //由于记录了fa[p]是p的父亲，所以可以往回找 
    16.                 if(p == u) break; //环遍历完了 
    17.             }
    18.             return 1; //记录已经找到环 
    19.         }
    20.     }
    21.     return 0; //没找到就继续往下找 
    22. }

    一个一个考虑，先看直径不经过基环，这个比较好求。此基环树的直径为环上挂着的点的每一棵子树的最大直径，记为 res1，枚举环上的每一个点，深搜计算子树的直径 res1=max(d[u]+d[v]+w(u,v))。顺道求出以 u 为根的子树的最大深度 d[u]。

    1. inline void dfs(int u,int fa){
    2.     for(re int i(head[u]) ; i ; i=e[i].nxt){
    3.         int v = e[i].to,w = e[i].w;
    4.         if(inc[v] || v==fa) continue; //如果这个点在环上，或者搜到了父亲就不继续 
    5.         dfs(v,u); //往下搜 
    6.         res1 = max(res1,d[u]+d[v]+w); //求最大的直径 
    7.         d[u] = max(d[u],d[v]+w); //顺道记录下来以u为根的最大深度 
    8.     }
    9. }
    10.  
    11. rep(i,1,tot) dfs(cv[i],0);

    然后来看直径经过环。一个最简单的想法就是，暴力枚举删哪一条边， res[i] = max (r两个子树的深度 + 它们在环上的距离 )。则经过环的直径 res2 = min(res[i])。

    但这样做复杂度是 n^2 的，过不去本题。考虑如何进行优化。

    1.把边 (1,tot) 断开，tot 为环上有 tot 个点，预处理前缀长度。

    A[i] = max( 前缀中链的长度 + 节点树的深度 )。

    B[i] = max( 前缀中两棵树的深度 + 这两个节点之间的距离 )。

    2.把边 (1,tot) 断开，预处理后缀长度。

    C[i] = max( 后缀中链的长度 + 节点树的深度 )。

    D[i] = max( 后缀中两棵树的深度 + 这两个节点之间的距离 )。

    3.枚举断开环上的边 (i,i+1)，拼凑答案。

    res[i]=max(B[i],D[i+1],A[i]+C[i+1]+w(1,tot))

    则经过环的直径 res2=min(res[i])。

    注意，最后需要有个特判，断开 (1,tot) 这条边，需要加上一句话 res2=min(res2,B[tot])。

    那么基环树的直径就是 max(res1,res2)，这道题的答案就是 max(res1,res2)/2。

    1. double sum=0,mx=0;
    2.     rep(i,1,tot){ //预处理前缀 
    3.         sum += cw[i-1]; //sum就是链长的加和 
    4.         A[i] = max(A[i-1],sum+d[cv[i]]); //根据A数组的定义来推 
    5.         B[i] = max(B[i-1],mx+d[cv[i]]+sum); //这里很巧妙
    6.                                             //我们的mx记录的是i这个点之前的某一个点k的深度-k之前的链长 
    7.                                             //也就是说，我们要求B数组，可以用一个抵消的思想
    8.                                             //sum记录的是链长的加和，再加上mx，也就把k前面的链长消掉了
    9.                                             //最后剩的就是k的深度+k到i的链长+i的深度，与B数组定义相同 
    10.         mx = max(mx,d[cv[i]]-sum); //注意要更新mx 
    11.     }
    12.     sum = mx = 0;
    13.     double cn_1 = cw[tot]; //这里也很巧妙，把tot这个点的点权记录下来，也就是相当于把1和tot这条边断开 
    14.     cw[tot] = 0; //要把tot这个点点权清零 
    15.     drep(i,tot,1){ //预处理后缀，和前缀类似 
    16.         sum += cw[i];
    17.         C[i] = max(C[i+1],sum+d[cv[i]]);
    18.         D[i] = max(D[i+1],mx+d[cv[i]]+sum);
    19.         mx = max(mx,d[cv[i]]-sum);
    20.     }
    21.     double res;
    22.     rep(i,1,tot){
    23.         res = max(max(B[i],D[i+1]),A[i]+C[i+1]+cn_1); //上述所说的三段 
    24.         res2 = min(res2,res); //使res2最小化 
    25.     }
    26.     res2 = min(res2,B[tot]); //别忘了加上特判 
    27.     printf("%.1lf\n",max(res1,res2)/2);

    总代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define re register
    7. #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
    8. #define rep(a,b,c)  for(re int a(b) ; a<=(c) ; ++a)
    9. using namespace std;
    10. inline int read(){
    11.     int x=0,f=1;char ch=getchar();
    12.     while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    13.     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    14.     return x*f;
    15. }
    16. const int M = 2e5+10;
    17. int n;
    18. int head[M],vis[M],fa[M];
    19. int inc[M],cv[M],cw[M],w[M];
    20. double d[M],A[M],B[M],C[M],D[M];
    21. int cnt,tot,ans;
    22. double res1,res2=1e18;
    23. struct edge{
    24.     int to,nxt,w;
    25. }e[M];
    26. inline void add(int u,int v,int w){
    27.     e[++cnt].to = v;
    28.     e[cnt].w = w;
    29.     e[cnt].nxt = head[u];
    30.     head[u] = cnt;
    31. }
    32. inline bool find(int u){
    33.     vis[u] = 1; //这个点记录为走过 
    34.     for(re int i(head[u]) ; i ; i=e[i].nxt){
    35.         int v = e[i].to;
    36.         if(v == fa[u]) continue; //走到了父亲不行 
    37.         fa[v] = u;
    38.         w[v] = e[i].w; //将这条边的边权转化为儿子的点权，和树剖的转化类似 
    39.         if(!vis[v]) { if(find(v)) return 1; } //如果这个点没有走过而且后面能找到环，就一直往回return 
    40.         else{ //找到了环 
    41.             int p = u; //枚举环上的点 
    42.             while(1){
    43.                 inc[p] = 1; //inc[p]=1表示p在环上 
    44.                 cv[++tot] = p; //环上的点的编号，由于后面操作，我们需要重新编号 
    45.                 cw[tot] = w[p]; //环上这个编号点的点权 
    46.                 p = fa[p]; //由于记录了fa[p]是p的父亲，所以可以往回找 
    47.                 if(p == u) break; //环遍历完了 
    48.             }
    49.             return 1; //记录已经找到环 
    50.         }
    51.     }
    52.     return 0; //没找到就继续往下找 
    53. }
    54. inline void dfs(int u,int fa){
    55.     for(re int i(head[u]) ; i ; i=e[i].nxt){
    56.         int v = e[i].to,w = e[i].w;
    57.         if(inc[v] || v==fa) continue; //如果这个点在环上，或者搜到了父亲就不继续 
    58.         dfs(v,u); //往下搜 
    59.         res1 = max(res1,d[u]+d[v]+w); //求最大的直径 
    60.         d[u] = max(d[u],d[v]+w); //顺道记录下来以u为根的最大深度 
    61.     }
    62. }
    63. signed main(){
    64.     n=read();
    65.     rep(i,1,n){
    66.         int u=read(),v=read(),w=read();
    67.         add(u,v,w),add(v,u,w);
    68.     }
    69.     find(1);
    70.     rep(i,1,tot) dfs(cv[i],0);
    71.     double sum=0,mx=0;
    72.     rep(i,1,tot){ //预处理前缀 
    73.         sum += cw[i-1]; //sum就是链长的加和 
    74.         A[i] = max(A[i-1],sum+d[cv[i]]); //根据A数组的定义来推 
    75.         B[i] = max(B[i-1],mx+d[cv[i]]+sum); //这里很巧妙
    76.                                             //我们的mx记录的是i这个点之前的某一个点k的深度-k之前的链长 
    77.                                             //也就是说，我们要求B数组，可以用一个抵消的思想
    78.                                             //sum记录的是链长的加和，再加上mx，也就把k前面的链长消掉了
    79.                                             //最后剩的就是k的深度+k到i的链长+i的深度，与B数组定义相同 
    80.         mx = max(mx,d[cv[i]]-sum); //注意要更新mx 
    81.     }
    82.     sum = mx = 0;
    83.     double cn_1 = cw[tot]; //这里也很巧妙，把tot这个点的点权记录下来，也就是相当于把1和tot这条边断开 
    84.     cw[tot] = 0; //要把tot这个点点权清零 
    85.     drep(i,tot,1){ //预处理后缀，和前缀类似 
    86.         sum += cw[i];
    87.         C[i] = max(C[i+1],sum+d[cv[i]]);
    88.         D[i] = max(D[i+1],mx+d[cv[i]]+sum);
    89.         mx = max(mx,d[cv[i]]-sum);
    90.     }
    91.     double res;
    92.     rep(i,1,tot){
    93.         res = max(max(B[i],D[i+1]),A[i]+C[i+1]+cn_1); //上述所说的三段 
    94.         res2 = min(res2,res); //使res2最小化 
    95.     }
    96.     res2 = min(res2,B[tot]); //别忘了加上特判 
    97.     printf("%.1lf\n",max(res1,res2)/2);
    98.     return 0;
    99. }

     

  • 相关阅读:
    构建网络下载器：Wt库指南让您轻松获取豆瓣网的美图
    c++获取mac 下总物理内存、所使用内存、当前进程所使用内存
    iOS全埋点解决方案-APP和H5打通
    机器学习笔记：自监督学习
    兄弟DCP-7080激光打印机硒鼓清零方法
    Golang sync.WaitGroup
    【python与数据分析】Matplotlib数据可视化（续）
    1002 A+B for Polynomials
    Unity实现经验光照模型
    Ubuntu目录和linux内核文件用途
  • 原文地址：https://blog.csdn.net/glorious_dream/article/details/126372594