蒟蒻关于仙人掌树的两个问题,各位神犇麻烦出手相救~~
查看原帖
蒟蒻关于仙人掌树的两个问题,各位神犇麻烦出手相救~~
68611
xiaogongzhu楼主2020/6/13 08:43
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 51000
using 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++)//为什么不能从1开始? 
	{
		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]);//为什么不能去掉mymin? 
		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;
		}
	}
	id=ans=0;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

问题在代码里面斜杠标注

1.for那里为什么不能从1开始,就算重叠了感觉也没什么影响啊?(从1开始就wa掉了)

2.为什么不能去掉mymin? 直接else low[x]=dfn[y]?如果y不是x的爸爸且被访问过但是low[x]却小于dfn[y],不就是两环共边的情况吗?不符合仙人掌树的定义呀。

2020/6/13 08:43
加载中...