A Huster

0%

基环树初步

Posted on Valine:

预备知识

​ 说实话,基环树一般比较综合,所以一般只要就要具有图论基本知识便可以开始学习.

警告

​ 博主实力不足,如果出错,请用力D他 .

认识

​ 基环树,原体是树,有树上任意连一条边,就成了一个环,即基环树,一般特征,$n$个点$n$条边;

​ 由于有树的特征,所以经常会用一些树的算法来计算基环树;

基础的知识

找环

​ 寻找环,这是基环树的基础,也很简单.

​ 考虑记录每个点是否访问过,当再次经过这个点时,那么这个点就能找出这个环了.

​ 我们只要在dfs时记录点的前继即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void get_cir(int x,int y,int f){
	int temp=x;stk[++tot]=x;id[x]=tot;w[y]=f;
	do{
		temp=pre[temp];
		stk[++tot]=temp;
		id[temp]=tot;
	}while(temp!=y);
	sum[1]=w[y];
	for(int i=2;i<=tot;i++)
		sum[i]=sum[i-1]+w[stk[i-1]];
}//记录环 

bool dfs1(int x,int fa){
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==fa) continue;
		if(!vis[y]) {
			pre[y]=x,w[y]=edge[i].w;
			if(dfs1(y,x)) return 1;
		}else {
			get_cir(x,y,edge[i].w);
			return 1;
		}
	}
	return 0;
}//返回值为是否找到环

​ 这个是根据原理自己构造的,需要注意的是,环处理出来的前缀和终点不是该点,即$sum[i]$为从0点到$i+1$点的距离,所以记录环中第2个for循环就是讲$sum$数组循环移动一次,当然这是我自己构造而导致的$bug$,不过也并不碍事;

子树DP找直径以及最大深度

​ 这里应该是比较基础的,确实,两遍bfs或dfs理解很容易,但是相比之下,DP有更优的时间以及优秀的代码长度,所以DP找直径是必要的;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll f;

void dfs2(int x,int fa){
	ll other=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==fa||id[y]) continue;
		dfs2(y,x);
		f=max(f,root[x]+root[y]+edge[i].w);
		f=max(f,other+root[y]+edge[i].w);//更新直径 
		other=max(other,root[y]+edge[i].w);
		dep[x]=max(dep[x],dep[y]+edge[i].w);//深度更新 
	}
	root[x]+=other;
}//DP找直径以及最大深度

进阶结合

​ 基环树,最终都是在环上处理问题,通常处理路径长度问题,因为博主实力不足,目前见过两种,都总结下来;

set维护

​ Roads in the Kingdom

​ 王国有$n$座城市与$n$条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值

​ 显然,这是一道有基环树特征的题,考虑枚举拆除道路,即环上道路(不在环上就不连通了),那么如何快速求出直径是我们所需要的;

​ 我们可以先考虑直径不过环,那么可以先DP预处理出子树上直径,并同时处理出最大深度$dep$(后面要用).

​ 之后考虑环上直径,我们可以维护环上前缀和,注意前缀和$sum[i]$必须以点$i$结尾;那么,直径公式就很显然了;

​ 那么,我们可以用两个set维护$sum[i]+dep[i]$和$-sum[i]+dep[i]$,每次取出最大值,相加即可;

​ 还有一些细节问题需要注意:

1.显然$i\not =j$,如果相等,我们可以取次小值最大的更新.

2.万一不在一个环上怎么办,我们知道,环上有两种求直径, $sum[j]-sum[i]$ 和 $sum[tot]-sum[j]+sum[i]$,那么我们如何保证一定是第一个公式呢.考虑我们在存前缀和时,$sum[1]$是点$1$与点$tot$之间的距离,那么我们可以先枚举这条边,那么,此时一定是第一个公式,这个可以想一想环上前缀和的特点;那么我们就可以在枚举点,枚举的边即为它与$i-1$之间的边,每次到下一个点,使我们这个点的$sum$加上$sum[tot]$,即相当于变成了前缀和最后一个点,然后在set中加入,并删除以前的;

3.如何保证$j>i$,考虑一下,如果 $jsum[j]$ ,那么显然

而我们求出的是最优的,所以一定是后者,所以只要注意一下第一条所说的$i=j$的情况,其他情况下$i<j$.

这样应该就能解决了,对了,multiset的结构体删除请注意一下,重载运算符可能会出差错;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
#define maxn 400007
#define ll long long
#define mp(x,y) (d){x,y}
#define st multiset<d>::iterator
using namespace std;
int n,head[maxn],pre[maxn],stk[maxn],id[maxn],tot;
int cent,vis[maxn],w[maxn];
ll sum[maxn],ans,dep[maxn],root[maxn];
struct node{
	int next,to,w;
}edge[maxn<<1];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
	type_of_scan f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
template<typename top,typename... tops>
inline void scan(top &x,tops&... X){
	scan(x),scan(X...);
}

inline void add(int u,int v,int w){
	edge[++cent]=(node){head[u],v,w};head[u]=cent;
	edge[++cent]=(node){head[v],u,w};head[v]=cent;
}

void get_cir(int x,int y,int f){
	int temp=x;stk[++tot]=x;id[x]=tot;w[y]=f;
	do{
		temp=pre[temp];
		stk[++tot]=temp;
		id[temp]=tot;
	}while(temp!=y);
	sum[1]=w[y];
	for(int i=2;i<=tot;i++)
		sum[i]=sum[i-1]+w[stk[i-1]];
}//记录环 

bool dfs1(int x,int fa){
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==fa) continue;
		if(!vis[y]) {
			pre[y]=x,w[y]=edge[i].w;
			if(dfs1(y,x)) return 1;
		}else {
			get_cir(x,y,edge[i].w);
			return 1;
		}
	}
	return 0;
}//返回值为是否找到环 

ll f;

void dfs2(int x,int fa){
	ll other=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==fa||id[y]) continue;
		dfs2(y,x);
		f=max(f,root[x]+root[y]+edge[i].w);
		f=max(f,other+root[y]+edge[i].w);//更新直径 
		other=max(other,root[y]+edge[i].w);
		dep[x]=max(dep[x],dep[y]+edge[i].w);//深度更新 
	}
	root[x]+=other;
}//DP找直径以及最大深度 

struct d{
	ll val,pos;
	bool operator <(const d &x) const{
		return val>x.val;
	}
};

multiset<d>a,b;

int main(){
	scan(n);ans=2305843009213693652;
	for(int i=1,u,v,w;i<=n;i++) scan(u,v,w),add(u,v,w);
	dfs1(1,0);
	for(int i=1;i<=tot;i++) dfs2(stk[i],0);
	for(int i=1;i<=tot;i++)
		a.insert(mp(sum[i]+dep[stk[i]],i)),b.insert(mp(-sum[i]+dep[stk[i]],i));
	for(int i=1;i<=tot;i++){
		st x=a.begin(),y=b.begin();
		ll ol=0;
		if(x->pos==y->pos){
			st dir=a.begin();dir++;
			ol=dir->val+y->val;
			dir=b.begin();dir++;
			ol=max(ol,dir->val+x->val);
		}else ol=x->val+y->val;
		ans=min(ans,ol);
		x=a.find(mp(sum[i]+dep[stk[i]],i)),y=b.find(mp(-sum[i]+dep[stk[i]],i));
		a.erase(x),b.erase(y);
		a.insert(mp(sum[i]+sum[tot]+dep[stk[i]],i)),b.insert(mp(-sum[i]-sum[tot]+dep[stk[i]],i));
	}
	printf("%I64d\n",max(f,ans));
}

单调队列优化

​ P4381 [IOI2008]Island

你准备浏览一个公园，该公园由 $N$ 个岛屿组成，当地管理部门从每个岛屿 $i$ 出发向另外一个岛屿建了一座长度为$L_i$的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：

  • 可以自行挑选一个岛开始游览。

  • 任何一个岛都不能游览一次以上。

  • 无论任何时间，你都可以由当前所在的岛 $S$ 去另一个从未到过的岛 $D$。从 $S$ 到 $D$

    有如下方法：

    • 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
    • 渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 $S$ 走到 $D$ (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

​ 我们很容易分析出这是一个基环树森林,分别计算每一个基环树上的直径,但是我们不能排除环的干扰,难道要暴力枚举环上边,博主并没有尝试,决定口胡;

set

​ 以下为博主口胡部分(并不是主流的正解做法):

​ 根据公式$d=sum[j]-sum[i]+dep[i]+dep[j]$;

​ 我们可以用上面的方法枚举断边,然后用set维护,求出最大直径,之后对于每一个基环树进行操作,累加和即可.

​ 总时间复杂度$O(nlongn)$,估计可以通过此题,但是因为这道题时间太过久远,博主在之前写过单调队列,已经不想再写一遍了,不过这种方法预测可行(还挺具有普适性的);

主流的单调队列

​ 显然,我们可以枚举点$i,j$,不过这样会$T$,

​ 但是考虑当$i<j$时,我们可以用单调队列维护$-sum[i]+dep[i]$的最大值,然后断环成链,更新即可

​ 至于出队条件,即为$pos[j]-pos[front]>len$($len$为环长度).时间复杂度$O(n)$.

​ 这里不再附上代码,因为当时代码太丑,有很大一部分是与他人代码雷同(因为当时不会写),为了防止误导,就不再附上代码;

ps:当遇到这类题时会再次update.

本站访问次数：