糖尿病康复,内容丰富有趣,生活中的好帮手!
糖尿病康复 > 仙人掌树学习1:仙人掌图 洛谷:[SHOI]仙人掌图 II

仙人掌树学习1:仙人掌图 洛谷:[SHOI]仙人掌图 II

时间:2022-05-01 01:26:55

相关推荐

仙人掌树学习1:仙人掌图	洛谷:[SHOI]仙人掌图 II

首先来看一下题目

【问题描述】

如果某个无向连通图的任意一条边至多只出现在一条简单回路(simplecycle)里,我们就称这张图为仙人图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)、(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,4),而(2,3)同时出现在前两个的简单回路里。另外,第三张图也不是仙人图,因为它并不是连通图。

显然,仙人图上的每条边,或者是这张仙人图的桥(bridge),或者在且仅在一个简单回路里,两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1,你的任务是求出给定的仙人图的直径。

【输入文件】

输入的第一行包括两个整数n和m(1≤n≤50,000以及0≤m≤10,000)。其中n代表顶点个数,我们约定图中的顶点将从1到n编号。

接下来一共有m行。代表m条路径。每行的开始有一个整数k(2≤k≤1000),代表在这条路径上的顶点个数。接下来是k个1到n之间的整数,分别对应了一个顶点,相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次,比如对于第一个样例,第一条路径从3经过8,又从8返回到了3,但是我们保证所有的边都会出现在某条路径上,而且不会重复出现在两条路径上,或者在一条路径上出现两次。

【输出文件】

只需输出一个数,这个数表示仙人图的直径长度。

【样例1输入】

15 3

9 1 2 3 4 5 6 7 8 3

7 2 9 10 11 12 13 10

5 2 14 9 15 10

【样例1输出】

8

【样例2输入】

10 1

10 1 2 3 4 5 6 7 8 9 10

【样例2输出】

9

对第一个样例的说明:

如图,6号点和12号点的最短路径长度为8,所以这张图的直径为8。

使用Pascal语言的选手请注意:

你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小,可以在程序的开头填加一句:{$M 5,000,000},其中5,000,000即指代栈空间的大小,请根据自己的程序选择适当的数值。

解题思路:

我们先不管这棵树里面有没有环,假设它就是正正常常的一棵树,那我们会怎么做?

如果解法是从上往下的,那么每到一个点都要往下访问一遍,然后将结果上传,让父亲自己斟酌。点太多了,时间和空间都搞不过来,而且下面的点会被不断地重复访问。pass那么只能从下往上考虑了。每个点的任务是完成两件事情:1.我最底可以到达哪里 2.有没有一条经过我的路径比较长。完成这两个任务的基础都是,我儿子的信息都已经在我手里了。画个图解释一下。

在这幅图中F即为最低可到达的深度,最底层的点自然没有深度。如果当前正在进行操作的点是X,且它的儿子分别是Y1,Y2,Y3.

通过之前的操作我们已经了解到,y1的深度是1,y2的深度是2,y3的深度是1,这些都是可以为X所用的信息。

X的最深深度只用继承儿子中最深的深度然后+1即可。在这幅图中,X的深度是Y2深度+1,所以X可以到达的最深深度是3.

现在考虑经过X的的最长路径。易得最长路径就是X到达底层的最长路径和X到达底层的次长路径之和。

如果没有环的话。整棵树跑一遍这个操作答案就出来了。

可问题的关键就是这棵树就是有环……呵……呵呵……呵呵呵……呵呵呵呵……环……

事情就开始变得有点(非常)啰嗦

棘手点如下:

继承方面遇到的困难:如果没有环,我直接拿我儿子的信息去更新我的F值就好了。可是因为有环。我就不能直接这么干,我怎么知道我的儿子会不会连着我的祖宗,然后我继承了我祖宗的信息,问题的关键是祖宗的信息应该是我给他的??!!……@#%¥……@#¥(我想起了一个悖论:我坐着时光飞机回到过去,把正是8岁的祖母给杀了,那么……我是哪来的?)这种感觉就和带环树有点像,当然这个类比可能不太恰当,不过只要知道这种情况坚决不能让它发生就好。统计经过我的最长路径方面遇到的困难:如下图,假设红色边是新加的一条边,在加上这条边之前经过X点的最长路径,就是X到底的最长路径(c+d+e)加上X到底的次长路径(a+b)长度是(a+b+c+d+e=5)可是这并不是1号点到2号的最短路径,我们发现它们之间还有另一条(a+f+d+e=4)的路径,这时候,树直径的更新就不能由X点来进行了。

难道我们刚才的思路就这样废了吗?NO!NO!NO!

针对第一个棘手点:

虽然我的儿子有跟我在同一环的可能性,但是我跟他也有可能不在同一个环里,这时候我就可以很安心地当他爸爸,直接拿他的信息来更新自己。

当我和我的儿子在同一环里的时候,我们就不要争着谁当谁的老爸。我们直接认环里认定一点当作整个环里其他点的爸爸,整个环里的点都是他的儿子,其他点的信息也全都存在他那里,这样他也好向上级汇报。

所以我只需要装一个环的识别器,平时就普通操作,一旦识别到这部分是环,我就进行另一种操作。

针对第二个棘手点:

同样是加装一个环的识别器,如果是一个普通的点就进行普通的操作,如果是一个环,我们就把一个环当作一个整体去操作。

怎么说?我们只要任意地找环里两个点(假设是A、B),已知这两个点到底层的最深深度,分别是FA,FB,然后我们再看A在环里到达B的最短距离d(因为是环,所以有两条边可以走),那么最长路径的更新就是 FA+FB+d。

通过上述操作我们发现,环在操作中的整体作用已经变化为一个点,因为向上汇报信息的时候,是环中的长老作为代表汇报环中的全部信息。最长路径的更新——是经过这个环的最长路径,这和经过X点的最长路径是同理的。

问题接着推进,

1.刚刚说的那个“环的识别器”怎么实现?

2.如何将环内信息存在长老那里?

3.环内最长路径两两找点更新绝逼超时,如何优化?

针对第一个问题,要装一个“环的识别器”,那么我们思考一下环有什么特征让我们能够识别它?

不就是沿着儿子的方向走可以走到自己嘛!

dfs中我们规定不可以从自己走向父亲(原路返回),让原本无向的仙人掌树变成一个有向图,如果在这种情况下还能有一部分的点可以互相到达,那么说明这些点在一个环里。

想到什么了没有?!对呀,在有向图中找到点可以相互到达,这不就强连通嘛!我们所谓的环不就是连通分量了嘛!

因此环的识别器就是融入强连通,你可能会问仙人掌树不是无向图、强连通不是有向图吗?可是我们dfs的时候是不能让X回到父亲那里去的,不然就会死循环,因此跑树的过程是一个有向图的形式,我们就可以放心地强连通了。

针对第二个问题,

我们更新普通点的F值,操作语句是:F[X]=MAX(F[Y]+1),就是儿子中取最大的F值+1.

为什么是+1?因为儿子与我只连着一条边,所以我到底层的最长路径就是(我走到儿子+儿子走到底层的路径)

那么环呢?因为环里的其他点都是我的儿子,所以我跟儿子的连边可能不止一条,就不能粗暴地+1了,所以环内长老到底层的最长路径就是:我在环内走到儿子的最短距离(环内从一点到另一点有两条路径,一条顺时针,一条逆时针)+儿子走到底层的最长路径(F[X]=MAX(F[Y]+MIN(X->Y)))

针对第三个问题:

如果我们不进行任何优化的话,思路就是:先把环给double成线状,然后for。什么叫double成线状?如下图,展开以后我们就可以很方便的往后取数操作,例如我要5连着后面6个,就是 5、6、7、8、1、2,它可以在一条线上体现。

那么环上任意找两个点更新最长路径的操作就变成:

for(int i=1;i<=tot*2;i++){for(int j=i+1;j<=tot*2;j++){if(j-i>tot/2)break;ans=max(ans.f[i]+f[j]+j-i);}}

(第三行if语句就是确保从x-->y走的边数不超过环内的一半,也就是走最短路径)

谁都看出来这样会超时。同时我们发现,J是I 后面的连续几个元素,随着I 一个一个地往后,J的范围也在不断往后面退,但总得来说相邻两个I 所搜索到的J 有很大的重叠。而且我们仔细一想还发现它满足单调性,所以我们可以用单调队列将二维循环优化为一维循环。

list[1]=1;head=tail=1;for(int i=2;i<=2*tot;i++)//单调队列(将二维循环优化为一维循环),维护以本环为支点,将点四周的任意两条路径合并构成线段{while(head<=tail&&i-list[head]>tot/2)head++; //以超过tot/2为基准踢掉队头 int j=list[head];ans=max(ans,a[i]+a[j]+i-j);while(head<=tail&&i-list[tail]+a[list[tail]]<=a[i])tail--;/*这里可以有两种理解方式:(其实都一样) 1.方程原为 max(f[j]+f[i]+i-j), 固定i之后就是求 max(f[j]-j) 即移过来的:a[list[tail]]-list[tail]<=a[i]-i 2.画一个图就可得知:对于不为i或j的任意节点(设为x)j与x合并线段为:f[j]+i-j+x-i+f[x],i与x合并线段为:f[i]+x-i+f[x] x-i+f[x]为公共部分,所以只要当 f[j]+i-j <= f[i] 时即可踢掉j 即 i-list[tail]+a[list[tail]]<=a[i]*/ list[++tail]=i;}

呈上完整代码

#include<cstdio>#include<cstring>#include<algorithm>#define N 51000using namespace std;struct node{int y,next;}a[410000];int last[N],len;inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;len++;a[len].y=x;a[len].next=last[y];last[y]=len;}inline int read(){char c=getchar();int s=0,f=1;while(c<'0' || '9'<c){if(c=='-')f=-1;c=getchar();}while('0'<=c && c<='9'){s=s*10+c-'0';c=getchar();}return f*s;}int ans=0,low[N],dfn[N],f[N],fa[N],deep[N],id,e[2*N],list[2*N],head,tail;inline int mymin(int x,int y){return x<y?x:y;}inline int mymax(int x,int y){return x>y?x:y;}inline void dp(int root,int x){int tot=deep[x]-deep[root]+1;for(int i=x;i!=fa[root];i=fa[i])e[tot--]=f[i];tot=deep[x]-deep[root]+1;for(int i=1;i<=tot;i++)e[i+tot]=e[i];head=tail=1;list[1]=1;for(int i=2;i<=tot*2;i++) {while(head<=tail && i-list[head]>tot/2)head++;ans=mymax(ans,e[list[head]]+e[i]+i-list[head]);while(head<=tail && e[list[tail]]-list[tail]<=e[i]-i)tail--;list[++tail]=i;}for(int i=2;i<=tot;i++)f[root]=mymax(f[root],e[i]+mymin(i-1,tot-i+1));}inline void dfs(int x){dfn[x]=low[x]=++id;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y==fa[x])continue;if(!dfn[y]){fa[y]=x;deep[y]=deep[x]+1;dfs(y);low[x]=mymin(low[x],low[y]);}else low[x]=mymin(low[x],dfn[y]); if(low[y]>dfn[x]){ans=mymax(ans,f[y]+f[x]+1);f[x]=mymax(f[x],f[y]+1);}}for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(fa[y]!=x && dfn[x]<dfn[y])dp(x,y);}}int main(){int n=read(),m=read();for(int i=1;i<=m;i++){int x,y,k;k=read();x=read();for(int j=2;j<=k;j++){y=read();ins(x,y);x=y;}}ans=id=0;dfs(1);printf("%d\n",ans);return 0;}

如果觉得《仙人掌树学习1:仙人掌图 洛谷:[SHOI]仙人掌图 II》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。