树的优化算法代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】树的优化算法

作者:玉洁 / 发布于2016/3/17/ 686

//最大顶点独立集
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;
}

试试其它关键字

同语言下

可能有用的

玉洁贡献的其它代码(6)