2017-03-19

【bzoj1023】cactus仙人掌图

仙人掌系列第一题

AC通道

求仙人掌直径，仙人掌经典问题之一。

在仙人掌上做dp即可。

错误记录：dfs缩环过程变量名打错，查了一个小时

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<vector>
#define FILE "read"
#define MAXN 100010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct node{int y,next,v;}e[MAXN<<2];
int n,m,cnt,bcnt,top,ans,dfs_clock,len(1),Link[MAXN],dfn[MAXN],f[MAXN],lenth[MAXN],dis[MAXN],q[MAXN<<1],p[MAXN<<1];
vector<int>ring[MAXN<<2];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getc();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
	return x*f;
}
void insert(int x,int y,int v){
	e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
	e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=v;
}
void dfs(int x,int fa){
	dfn[x]=++dfs_clock;
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
		if(!dfn[e[i].y])  q[++top]=i,dfs(e[i].y,x),--top;
		else if(dfn[e[i].y]<dfn[x]){
			ring[++bcnt].push_back(i);
			for(int j=top;j;--j){
				if(e[q[j]].y==e[i].y)  break;
				ring[bcnt].push_back(q[j]);
			}
		}
	}
}
void build(){
	for(int k=1;k<=bcnt;++k){
		int size=ring[k].size(),top=e[ring[k][0]].y;
		for(int i=0;i<size;++i){
			int temp=e[ring[k][i]].y;  
			lenth[k]+=e[ring[k][i]].v;  dis[i+1]=lenth[k];
			e[ring[k][i]].y=e[ring[k][i]^1].y=0;
			ring[k][i]=temp;
		}insert(++cnt,top,0);
		for(int i=1;i<size;++i)  insert(ring[k][i],cnt,min(dis[i],lenth[k]-dis[i]));
	}
}
void dp(int x,int fa){
	for(int i=Link[x];i;i=e[i].next)if(e[i].y&&e[i].y!=fa){
		dp(e[i].y,x);
		if(x<=n)  cmax(ans,f[x]+f[e[i].y]+e[i].v);
		cmax(f[x],f[e[i].y]+e[i].v);
	}
}
void dp(){
	for(int k=1;k<=bcnt;++k){
		int size=ring[k].size(),top=ring[k][0],temp=f[top];f[top]=0;
		for(int i=0;i<size;++i)  p[i+1]=p[i+size+1]=ring[k][i];
		for(int i=1,head=1,tail=0;i<=size*2;++i){
			while(head<=tail&&i-q[head]>(size>>1)) ++head;
			if(head<=tail)  cmax(ans,i-q[head]+f[p[i]]+f[p[q[head]]]);
			while(head<=tail&&f[p[q[tail]]]-q[tail]<=f[p[i]]-i) --tail;
			q[++tail]=i;
		}f[top]=temp;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=cnt=read();  m=read();
	for(int i=1;i<=m;++i){
		int T=read(),temp=read();
		for(int j=1,t;j<T;++j) insert((t=read()),temp,1),temp=t;
	}
	dfs(1,0);  build();  dp(1,0);  dp();
	printf("%d\n",ans);
	return 0;
}

本文标题:【bzoj1023】cactus仙人掌图

文章作者:chty

发布时间:2017年03月19日 - 21时31分

最后更新:2018年03月02日 - 18时10分

许可协议:本文为博主原创，未经许可不得转载。