发布于

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;
}
发布于

lp2515 HAOI2010 软件安装

简单的tarjan缩点+树形背包DP。
考虑N<=100，M<=500，只需要设f[i][j]表示第i个点，已用j的容量。
然后直接DP即可。
特别地，由于如果某一个点的子树中的点被选中了，这个点也要被选中，所以我们在计算每个点的时候，一定要将这个点加进去。
然后仔细看看这道题，发现它不保证没有环！
这下完蛋了，咋做啊？
考虑到这个环要么都选，要么都不选，所以可以先用tarjan找环，把找环后的点拿来dfs。
然后我们考虑一个性质：如果存在环，那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度，然后将入度为0的点连向虚点0。这样只需要一次DP。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
	vis[X]=1,dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	for(int i=g[X];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
		}else if(vis[e[i].v]){
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
	if(dfn[X]==lw[X]){
		++ccnt;
		while(st[tp+1]!=X){
			clr[st[tp]]=ccnt;
			val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
			vis[st[tp]]=0;
			--tp;
		}
	}
}
inline void dfs1(int X){
	for(int i=ww[X];i<=m;++i){
		f[X][i]=val[X];
	}
	for(int i=h[X];i;i=e[i].nxt){
		dfs1(e[i].v);
		for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。 
			for(int k=0;k<=j;++k){//k表示这棵子树的重量和。 
				f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]); 
			}
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		if(d[i]){
			add(g,d[i],i);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			dfs0(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(clr[d[i]]!=clr[i]){
			add(h,clr[d[i]],clr[i]);
			++in[clr[i]];
		}
	}
	for(int i=1;i<=ccnt;++i){
		if(!in[i]){
			add(h,0,i);
		}
	}
	dfs1(0);
	printf("%d\n",f[0][m]);
}
int main(){
	init();
	return 0;
}