新建 文本文档 (2).txt

最小权点覆盖问题用分支限界实现,对于给定的无向图G,计算G的最小权点覆盖.

class BoardNode {
	friend int BBArrange (int**,int,int,int*&);
public :
	operator int () const {return cd;}
	int len () ;
private :
	int *x,s,cd,*low,*high;
}


int BoardNode :: len()
{
	int tmp = 0 ;
	for (int k=1;k<=m;k++)
		if (low[k]<=n&&high[k]>0&&tmp<high[k]-low[k])tmp=high[k]-low[k];
	return tmp ;
}

int BBArrange (int **B ,int n, int m, int *&bestx)
{
	MinHeap<BoardNode>H(2000000);
	BoardNode E;
	E.x=new int[n+1];
	E.s=0 ; E,cd=0 ; E.low=new int[m+1];
	for (int i =1 ; i<=m ; i++) {E.high[i]=0;E.low[i]=n+1;}
	for (int i =1 ; i<=n ; i++) E.x[i]-i;
	int bestd=n+1;
	bestx=0;
	do{
		if(E.s==n-1){
			for (j=1;j<=m;j++)
				if (B[E.x[n][j]&&n>E.high[j])E.high[j]=n;
			int Id=E.len();
			if(Id<bestd){
				delete[]bestx;
				bestx=E.x;
				bestd=Id;
			}

			else {
				int curr =E.s+1;
				for (int i-E.s+1;i<-n;i++){
					BoardNode N;
					N.low =new int[m+1];
					N.high=new int[m+1];
					for (int j=1;j<=m;j++){
						N.low[j]=E.low[j];N.high[j]=E.high[j];
						if(B[E.x[i][j]){
							if(curr<N.low[j])N.low[j]=curr;
							if(curr>N.high[j])N.high[j]=curr;
						}
					}
					N.cd=N.len();
					if(N.cd<bestd){
						N.x=new int [n+1];
						N.s=E.s+1;
						for (int j=1 ; j<=n ; j++)N.x[j]=E.x[j];
						N.x[N.s]=E.x[i];
						N.x[i]=E.x[N.s];
						H.Insert(N);
					}
					else {delete[]N.low;delete[]N.high;}
				}
				delete []E.x;
			}
			try {H.DeleteMin(E);}
			catch(OutOfBounds){return bestd;}
		}while (E.cd<bestd);
		do {
			delete[]E.x;
			delete[]E.low;
			delete[]E.high;
			try {H.DeleteMin(E);}
			catch (...){break;}
		}while (ture);
		return bestd;
	}