lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图,它在许多方面都有树的性质,只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树,我们发现,非环节点的转移都是非常容易达成了,问题在于环上的节点的转移。

首先,我们要找到这个环,这可以用Tarjan算法来完成。
具体来说,我们维护两个数组:dfn和lw,其中前者表示的是某一个节点的dfs序,后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然,在搜索中,如果下一个节点未被访问过,我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则,当前节点通向它的边一定是一条返祖边或者父亲边,那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环,我们如果将它视为一个节点,我们想一想要怎么从它的「孩子」们处转移呢?
我们发现,依次枚举它的每一个孩子,答案显然是:
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

#include<iostream>
#include<cstdio>
#include<deque>
#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int et=0,h[100005];
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值,从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}