040320141.cpp

优先队列式分支限界法园排列问题

/*************************
圆排列问题，用分枝限界法
学号：040320141
***************************/
#include<iostream.h>
#include<fstream.h>
#include<math.h>

char ifname[15]="input.txt";
char ofname[15]="output.txt";

const int num=100002; //定义堆的单元个数

struct MinHeapNode  //堆节点
{
	double privor;  //优先级
	int s;           //表示[1..s]已排好
	double * x;      //圆心坐标
	double * r;      //半径排列
};

MinHeapNode  MinHeap[num];  //堆

double min;         //最小限界
int clen;            //堆的长度
double * cir_r;      //半径
int n;               

template<class Type>
void swap(Type & a, Type & b)  //交换
{
	Type temp=a;
	      a=b;
	     b=temp;
}
void pushdown(MinHeapNode* x,int first,int last)  //最xiao堆
{
	int r;
	 r=first;
	while(r<=(last/2) )
	{
		if(2*r==last)
		{
			if(x[r].privor>x[2*r].privor) 
			{
				swap(x[r],x[2*r]);				
			};
		break;
		}
      else if((x[r].privor>x[2*r].privor)&&(x[2*r].privor<=x[2*r+1].privor))
	  {   
		  swap(x[r],x[2*r]);         
		  r=2*r;
	  }
	  else if((x[r].privor>x[2*r+1].privor)&&(x[2*r+1].privor<x[2*r].privor))
	  {
          swap(x[r],x[2*r+1]);       
		  r=2*r+1;
	  }
	  else  break;
	};
}

void   MinHeapInsert(MinHeapNode N, int len)  //堆插入
{   
	int i;
    MinHeap[len].x=new double[n+1];
    MinHeap[len].r=new double[n+1];

	for(i=1;i<=n;i++)
	{
	 MinHeap[len].x[i]=N.x[i];
     MinHeap[len].r[i]=N.r[i];
	}

     MinHeap[len].s=N.s;
     MinHeap[len].privor=N.privor;

	pushdown(MinHeap,1,len);
	swap(MinHeap[1],MinHeap[len]);	
}

double center(MinHeapNode N,int t)   //圆的中心坐标计算
{   
	int j;
	double temp=0.0;
	for( j=1;j<t;j++)
	{
		double valuex=N.x[j]+2.0*sqrt(N.r[t]*N.r[j]);
		if(valuex>temp) temp=valuex;
	};
	return temp;
}

void main()
{   

	int i,j;
	ifstream fin(ifname);
	if(fin.fail()==0)
	{
		ofstream out(ofname);
		fin>>n;
     
		cir_r=new double[n+1];
       
		for(i=1;i<=n;i++)		
		   fin>>cir_r[i];
		  		     
		min=10000000000.0;
		clen=0;

        MinHeapNode E;
        E.x=new double[n+1];
        E.r=new double[n+1];
		for(i=1;i<=n;i++)
        E.r[i]=cir_r[i];
			
        E.x[1]=0;
		E.s=0;
		E.privor=0.0;
		for(j=1;j<=n;j++)
          E.privor+=E.r[j];
		do
		{
          if(E.s==n-2)         //叶节点
		  {  
			  E.x[n-1]=center(E,n-1);
              E.x[n]=center(E,n);
             
			  double low=0.0;
			  double high=0.0;
			  for( j=1;j<=n;j++)
			  {
				  if(E.x[j]-E.r[j]<low) low=E.x[j]-E.r[j];
                  if(E.x[j]+E.r[j]>high) high=E.x[j]+E.r[j];
			  }
			  if((high-low)<min)  min=high-low;  //更新min
			  //break;
		  }
	  else 
	  { 

           if(E.s==0)   //解决镜像对称问题
			{
				for(i=1;i<=n-1;i++)
				{
					MinHeapNode N;
					N.s=1;
					N.r=new double[n+1];
					N.x=new double[n+1];
					for(j=1;j<=n;j++)					
						N.r[j]=E.r[j];					
					
					N.r[N.s]=E.r[i];
					N.r[i]=E.r[N.s];
			
		             N.x[N.s]=0.0;
                       
					 N.privor=E.privor-E.r[i];
                  
					for(int k=i+1;k<=n;k++)
					{
						swap(N.r[k],N.r[n]);					
						clen++;						
						MinHeapInsert(N,clen);
                        swap(N.r[k],N.r[n]);
					};
					delete N.r;
					delete N.x;
				}						
			}
		   else
		   {
			  for(i=E.s+1;i<=n-1;i++)
			  {    
				 if((i==E.s+1)||(E.r[i]!=E.r[E.s+1]))  //解决相同圆的问题
				 {
					 
                 MinHeapNode N;
			     N.x=new double[n+1];
				 N.r=new double[n+1];
				 N.s=E.s+1;
                 for( j=1;j<=n;j++)
					N.r[j]=E.r[j];

				 N.r[N.s]=E.r[i];
                 N.r[i]=E.r[N.s];
                  
                 double rlen=0.0;
				 for( j=N.s+1;j<=n;j++)				
					 rlen+=N.r[j];

                double  min_len=N.r[n]/2;///
				 for(j=N.s;j<n;j++)///
					 min_len+=sqrt(N.r[j]*N.r[j+1]);///
                     
			//	   rlen=min_len;/////
				
				 for(j=1;j<=E.s;j++)
					 N.x[j]=E.x[j];

				  N.x[N.s]=center(N,N.s);

           // N.privor=N.x[N.s]+N.r[1]+N.r[n]+ rlen;
				 
                N.privor=N.x[N.s]+N.r[1]+N.r[N.s]+rlen;
				
				  if(N.x[N.s]+N.r[1]+2.0*sqrt(N.r[N.s]*N.r[N.s+1])+rlen+min_len/8<min)
                 // if(N.x[N.s]+N.r[1]+min_len<min)
				   {			     		
						 if(clen>=100000)						
							 break;						 
                         clen++;
                         MinHeapInsert(N,clen);			         	                                     				
				   }                   				  
			 		  delete N.r;
                      delete N.x;
			  }
			 }
		}
	  }           
             if(clen==0)break;
              E=MinHeap[clen];
        //   delete MinHeap[clen].r;
		//	  delete MinHeap[clen].x;
              clen--;			 
		}while(clen>=0);
        if(n==1)  min=2*cir_r[1];
       out<<min<<endl;
	}
}