040320131.cpp

分支限界法解圆排列问题

#include <queue>
#include <fstream>
#include<iostream>
#include <math.h>
#include <time.h>
using namespace std;
double **dic;//dic[i][j]存放第i个圆与第j个圆得圆心
double *r;//存放n个圆的半径
double best;


template<class type>
int partition (type a[],int low,int high){
	int pivotpos=low;
	type pivot=a[low];
    for (int i=low+1;i<=high;i++)
		if (a[i]<pivot&&++pivotpos!=i)
			swap(a[pivotpos],a[i]);
		swap(a[low],a[pivotpos]);
		return pivotpos;}
template<class type>
void quicksort (type a[],int p,int r){
	int i;
	if(p<r)
	{i=partition(a,p,r);
	quicksort(a,p,i-1);
	quicksort(a,i+1,r);}}
class circlenode
{
	friend void circleperm(double *r,int n);
	
private:
	int mink;//代排的圆中第mink个圆的半径最小
	int s;//算法完成了s步，即排好了s个圆
	int k;//镜像剪枝
	double *x;//圆心坐标
	int *rp;//所选的第s个圆得半径为r[rp[s]]
	double compute(int n);
	double center(int t);
	
};




double circlenode::compute(int n)
{
	int i;
	double low=0.0;
	double high=x[n-1]+r[rp[n-1]];
	for(i=0;i<n;i++)
	{
		if(x[i]-r[rp[i]]<low)
			low=(double)x[i]-r[rp[i]];
		if(x[i]+r[rp[i]]>high)
			high=(double)x[i]+r[rp[i]];
	}
	return (double)high-low;
};



double circlenode::center(int t)
{
	double temp=0.0;
	double valuex;
	for(int i=0;i<t;i++)
	{
		valuex=x[i]+(double)2*sqrt(r[rp[i]]*r[rp[t]]);
		if(valuex>temp)
			temp=valuex;
	}
	return temp;
};


void circleperm(double *r,int n)
{
	int i,j;
	int wk;
	int tag;
	int tt;
	double bestt;
	double *tsame;
	int tsamen;
	double rtemp;
	double mintemp;
	tsame=new double[n];
    queue<circlenode> qu;
	
	/*e.x=new double[n];
    e.s=-1;
	e.mink=0;
    e.rp=new int [n];
	for(i=0;i<n;i++)
	e.rp[i]=i;*/
	circlenode tempe;
	tempe.x=new double[n];
	tempe.rp=new int[n];
	int fi=0;
	int li=n-1;
	i=0;
	while(fi<=li)
	{
		tempe.rp[i]=fi;
		i++;
		fi++;
		if(fi<=li)
		{
			tempe.rp[i]=li;
			i++;
			li--;
		}
	}
	for(i=0;i<n;i++)
		tempe.x[i]=tempe.center(i);
	best=tempe.compute(n);//算初值
	/* for(i=0;i<n;i++)
	cout<<tempe.rp[i]<<" ";
	 cout<<endl;
	 
	 
      for(i=0;i<n;i++)
	{cout<<tempe.x[i]<<endl;}//test best*/
	
	delete []tempe.x;
	delete []tempe.rp;
	
	cout<<best<<endl;
	
	// best=12345;//需修改
	circlenode e;
	for(i=0;i<n-1;i++)
	{
		
		
		
		//cout<<r[i]<<endl;
		if(i>0&&r[i-1]==r[i]) continue;
		if(i==0) e.mink=1;
		else e.mink=0;
		e.k=n-i-1;//比i大的数字的个数
		e.rp=new int[n];
		e.x=new double[n];
		
		for(j=0;j<n;j++)
		{
			e.rp[j]=j;
			
		};
		e.x[0]=0;
		e.rp[0]=i;
		e.rp[i]=0;
		
		e.s=0;
		qu.push(e);
	}
	while(!qu.empty())
	{
		e=qu.front();
		qu.pop();
		if (e.s==n-3)
		{
			if(e.rp[n-1]>e.rp[0])
			{
				e.x[n-2]=e.center(n-2);
				e.x[n-1]=e.center(n-1);
				bestt=e.compute(n);
				
				
				
				
				if(bestt<best)
					best=bestt;
			}
			if(e.rp[n-2]>e.rp[0])
			{
				tt=e.rp[n-2];
				e.rp[n-2]=e.rp[n-1];
				e.rp[n-1]=tt;
				
				
				e.x[n-2]=e.center(n-2);
				e.x[n-1]=e.center(n-1);
				bestt=e.compute(n);
				
				
				if(bestt<best)
					best=bestt;
			}
		}
		else
		{
			
			tsamen=0;
			
			for(i=e.s+1;i<n;i++)
			{ 
				if(e.rp[i]>e.rp[0]) wk=e.k-1;
				else wk=e.k;
				
				if(wk) //镜像剪枝
				{
					
					tag=0;
					rtemp=r[e.rp[i]];
					for(j=0;j<tsamen;j++)
					{
						if(rtemp==tsame[j])
							tag=1;
						//	continue;
					}
					if(!tag)
					{
						
						tsame[tsamen]=rtemp;
						tsamen++;
						circlenode w;
						w.k=wk;
						w.s=e.s+1;
						w.x=new double[n];
						w.rp=new int[n];
						
						for(j=0;j<n;j++)
						{
							w.x[j]=e.x[j];
							w.rp[j]=e.rp[j];
						}
						
						
						w.rp[w.s]=e.rp[i];
						w.rp[i]=e.rp[w.s];
						
						w.mink=e.mink;
						if(w.mink==w.rp[w.s])
						{
							w.mink=w.rp[w.s+1];
							for(j=w.s+2;j<n;j++)
							{
								if(r[w.rp[j]]<r[w.mink])
									w.mink=w.rp[j];
							}
							
						}
						w.x[w.s]=w.center(w.s);
						mintemp=w.x[w.s]+(2*n-2*w.s-1)*r[w.mink]+r[w.rp[0]];
						if(mintemp<best)
						{
							qu.push(w);
						}
						else
						{
							delete []w.x;
							delete []w.rp;
						}
					}  //if(!tag)
				}//if(wk)
			}//for(i=e.s+1;i<n;i++)
			
		}//else
		delete []e.x;
		delete []e.rp;	
	}//while
	delete []tsame;
	
}
void main()
{
	clock_t start, finish;
	start=clock();
	fstream infile,outfile;
	int n;
	int i;
	int j;
	
	infile.open("input.txt",ios::in);
	outfile.open("output.txt",ios.out);
	infile>>n;
	r=new double[n];
	dic=new double*[n];
	for(i=0;i<n;i++)
		dic[i]=new double[n];
	for(i=0;i<n;i++)
		infile>>r[i];
	
    if(n==1)
	{
		best=2.0*r[0];
		outfile<<best<<endl;
		cout<<best<<endl;
	}
	else if(n==2)
	{
		double temp2;
		temp2=2*sqrt(r[0]*r[1]);
		double low2,high2;
		low2=0-r[0];
		if(temp2-r[1]<low2) low2=temp2-r[1];
		high2=temp2+r[1];
		if(high2<r[0]) high2=r[0];
		best=high2-low2;
		outfile<<best<<endl;
		cout<<best<<endl;
	}
	else
	{
		quicksort(r,0,n-1);
		/*	for(i=0;i<n;i++)
		cout<<r[i]<<endl;*/
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
				dic[i][j]=dic[j][i]=sqrt(r[i]*r[j]);
		}
		
		circleperm(r,n);
		outfile<<best<<endl;
		cout<<best<<endl;
	}
	infile.close();
	outfile.close();
	delete []r;
	for(i=0;i<n;i++)
		delete []dic[i];
	delete []dic;
	
	finish=clock();
	cout<<endl<<"Elapsed Time: "<<(double)(finish-start)/CLOCKS_PER_SEC<<" secouds"<<endl;
	
}