树的优化算法.txt

来自「ACM资料大集合」· 文本 代码 · 共 63 行

//最大顶点独立集
int max_node_independent(int n,int* pre,int* set){
	int c[MAXN],i,ret=0;
	for (i=0;i<n;i++)
		c[i]=set[i]=0;
	for (i=n-1;i>=0;i--)
		if (!c[i]){
			set[i]=1;
			if (pre[i]!=-1)
				c[pre[i]]=1;
			ret++;
		}
	return ret;
}

//最大边独立集
int max_edge_independent(int n,int* pre,int* set){
	int c[MAXN],i,ret=0;
	for (i=0;i<n;i++)
		c[i]=set[i]=0;
	for (i=n-1;i>=0;i--)
		if (!c[i]&&pre[i]!=-1&&!c[pre[i]]){
			set[i]=1;
			c[pre[i]]=1;
			ret++;
		}
	return ret;
}

//最小顶点覆盖集
int min_node_cover(int n,int* pre,int* set){
	int c[MAXN],i,ret=0;
	for (i=0;i<n;i++)
		c[i]=set[i]=0;
	for (i=n-1;i>=0;i--)
		if (!c[i]&&pre[i]!=-1&&!c[pre[i]]){
			set[i]=1;
			c[pre[i]]=1;
			ret++;
		}
	return ret;
}

//最小顶点支配集
int min_node_dominant(int n,int* pre,int* set){
	int c[MAXN],i,ret=0;
	for (i=0;i<n;i++)
		c[i]=set[i]=0;
	for (i=n-1;i>=0;i--)
		if (!c[i]&&(pre[i]==-1||!set[pre[i]])){
			if (pre[i]!=-1){
				set[pre[i]]=1;
				c[pre[i]]=1;
				if (pre[pre[i]]!=-1)
					c[pre[pre[i]]]=1;
			}
			else
				set[i]=1;
			ret++;
		}
	return ret;
}