#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>

class flowshop;//預(yù)先聲明作業(yè)調(diào)度類

//堆結(jié)點生成類
class minheapnode
{  
	friend flowshop;//友元類  

	public:
		operator int() const {return bb;}
		int bb;//當(dāng)前完成時間和下界
	private:
		void init(int);//最小堆結(jié)點初始化
		void newnode(minheapnode,int,int,int,int);//生成最小堆新結(jié)點的對象賦值函數(shù)
		int s;//已安排作業(yè)數(shù)
		int f1;//機器1上最后完成時間
		int f2;//機器2上最后完成時間
		int sf2;//當(dāng)前機器2上的完成時間和
		int *x;//當(dāng)前作業(yè)調(diào)度

 };


void minheapnode::init(int n)
{  //最小堆結(jié)點初始化
	x=new int[n];//分配x數(shù)組
	for(int i=0;i<n;i++)
		x[i]=i;//x數(shù)組初始化
	s=f1=f2=sf2=bb=0;//其他成員初始化
 }


 void minheapnode::newnode(minheapnode e,int ef1,int ef2,int ebb,int n)
 {  //最小堆新結(jié)點
	 x=new int[n];
	 for(int i=0;i<n;i++)
		 x[i]=e.x[i];
	 f1=ef1;
	 f2=ef2;
	 sf2=e.sf2+f2;
	 bb=ebb;
	 s=e.s+1;
 };


 //堆排序類
 class minheap
 {  
	private:
		minheapnode *heap;//堆數(shù)組
		int currentsize;//當(dāng)前堆元素個數(shù)
		int heapsize;//堆大小
		void filterdown(int start,int endofheap);//向下調(diào)整
		void filterup(int start);//向上調(diào)整
	public:
	    minheap(int n);//構(gòu)造函數(shù)
		~minheap();//析構(gòu)函數(shù)
		int insert(minheapnode& x);//插入函數(shù)
		int removemin(minheapnode& x);//刪除最小值函數(shù)
		int isempty();//判斷空函數(shù)
		int isfull();//判斷滿函數(shù)
		void makeempty();//置空函數(shù)
 };
 
 minheap::minheap(int n)
 {  
	 heapsize=n;//設(shè)置堆大小
	 currentsize=0;//設(shè)置0表示堆中無結(jié)點
	 if(!(heap=new minheapnode[heapsize]))//分配heap數(shù)組
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }
 }

 minheap::~minheap()
 {  
	 delete[] heap;//釋放heap數(shù)組所占內(nèi)存
 }

 /*判斷空函數(shù)的定義*/
 int minheap::isempty()
 {  
	 return currentsize==0;
 }
 
 /*判斷滿函數(shù)的定義*/
 int minheap::isfull()
 {  
	 return currentsize==heapsize;
 }
 
 /*置空函數(shù)的定義*/ 
 void minheap::makeempty()
 {  
	 currentsize=0;//設(shè)定0表示堆中無結(jié)點
 }
 
 /*向下調(diào)整函數(shù)的定義*/
 void minheap::filterdown(int start,int endofheap)
 {  
	 int i=start,j=2*i+1;//j是i的左子女
	 minheapnode temp=heap[i];//預(yù)先保存i位置的值
	 while(j<=endofheap)
	 {    
		 if(j<endofheap&&heap[j].bb>heap[j+1].bb) j++;//選出兩子女中更小值位置
		 if(temp.bb<=heap[j].bb) break;//如果比最小值更小則不需調(diào)整
		 else     
		 {      
			 heap[i]=heap[j];//將最小值移動到根位置
			 i=j;//設(shè)置新的根位置
			 j=2*j+1;//新的左子女位置，繼續(xù)向下調(diào)整
		 }
	 }  
	 heap[i]=temp;//將初始位置的結(jié)點移動到新位置
 }

 /*向上調(diào)整函數(shù)的定義*/ 
 void minheap::filterup(int start)
 {  
	 int j=start,i=(j-1)/2;//j是i的雙親
	 minheapnode temp=heap[j];//預(yù)先保存j位置的值
	 while(j>0)  
	 {    
		 if(heap[i].bb<temp.bb) break;//如果雙親更小則不需調(diào)整
		 else    
		 {      
			heap[j]=heap[i];//將最小值移動到雙親位置上
			j=i;//設(shè)置新的子女位置
			i=(i-1)/2;//新的雙親位置，繼續(xù)向上調(diào)整
		 }  
	 }  
	 heap[j]=temp;//將初始位置的結(jié)點移動到新位置
 }
 
 /*插入函數(shù)的定義*/
 int minheap::insert(minheapnode& x)
 {  
	 if(currentsize==heapsize)//堆已滿不能插入
	 {    
		 cout<<"堆已滿"<<endl;
		 return 0;
	 }	  
	 heap[currentsize]=x;//在堆尾插入元素
	 filterup(currentsize);//向上調(diào)整為最小堆
	 currentsize++;//元素個數(shù)加1
	 return 1;
 }
 
 /*刪除最小值函數(shù)的定義*/
 int minheap::removemin(minheapnode& x)
 {  
	 if(!currentsize)//堆空不能刪除
	 {     
		 cout<<"堆已空"<<endl;
		 return 0;   
	 }  
	 x=heap[0];//堆首元素賦給x
	 heap[0]=heap[currentsize-1];//堆尾元素移動到堆首
	 currentsize--;//元素個數(shù)減1   
	 filterdown(0,currentsize-1);//向下調(diào)整為最小堆
	 return 1;
 }

 
/*交換函數(shù)的定義*/
void swap(int& a,int& b)
{  int temp;
  temp=a;  
  a=b;
  b=temp;
}
 
 /*調(diào)度類*/ 
 class flowshop
 {  
	public:    
		void bbflow(void);//優(yōu)先隊列式分支限界法求解
		flowshop();//構(gòu)造函數(shù)    
		void outputtofile();//輸出解信息
	private:
		 int bound(minheapnode,int&,int&,bool **);//計算完成時間和下界
		 void sort(void);//排序
	     int n;//批處理作業(yè)個數(shù)
	     int **m;//個作業(yè)所需的處理時間數(shù)組     
		 int **b;//個作業(yè)所需的處理時間排序后數(shù)組
	     int **a;//數(shù)組m和b的對應(yīng)關(guān)系數(shù)組（a[i][j]=k表示作業(yè)i在數(shù)組b中的位置是k，即第k個處理）
	     int *bestx;//最優(yōu)解
		 int bestc;//最小完成時間和
		 bool **y;//y[i][j]表示作業(yè)i在機器j上是否已完成
 };


 /*排序函數(shù)的定義*/
 void flowshop::sort()//按照在機器1和機器2上的完成時間進(jìn)行遞增排序
 {  
	 int i,j,k;//循環(huán)控制變量
	 int *c;  
	 if(!(c=new int[n]))//分配c數(shù)組
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }  
	 for(j=0;j<2;j++)//b和c數(shù)組初始化
	 {    
		 for(i=0;i<n;i++)
		 {  
			 b[i][j]=m[i][j];
			 c[i]=i;
		 }   
		 for(i=0;i<n-1;i++)//冒泡排序趟數(shù)
			 for(k=n-1;k>i;k--)
				 if(b[k][j]<b[k-1][j])
				 {   
					 swap(b[k][j],b[k-1][j]);//交換b兩元素
					 swap(c[k],c[k-1]);//同時交換c
				 }    
				 for(i=0;i<n;i++) a[c[i]][j]=i;//設(shè)置m和b的關(guān)系數(shù)組a
	 }  
	 delete[] c;//釋放c所占內(nèi)存
 }
 
 /*計算下界函數(shù)的定義*/
 int flowshop::bound(minheapnode e,int& f1,int& f2,bool **y)
 {  
	 int j,k;//循環(huán)控制變量
	 for(k=0;k<n;k++)//y數(shù)組初始化
		 for(j=0;j<2;j++)
			 y[k][j]=false;
		 for(k=0;k<=e.s;k++)//設(shè)置已完成的作業(yè)標(biāo)志
			 for(j=0;j<2;j++)
				 y[a[e.x[k]][j]][j]=true;
		 f1=e.f1+m[e.x[e.s]][0];//當(dāng)前作業(yè)完成后機器1最后完成時間
		 f2=((f1>e.f2)?f1:e.f2)+m[e.x[e.s]][1];//當(dāng)前作業(yè)完成后機器2最后完成時間
		 int sf2=e.sf2+f2;//當(dāng)前作業(yè)完成后的完成時間和
		 int s1=0,s2=0,k1=n-e.s,k2=n-e.s,f3=f2;//初始化各變量
		 for(j=0;j<n;j++)//計算s1的值（機器1沒有空閑的下界）
			 if(!y[j][0])
			 {     
				 k1--; 
				 if(k1==n-e.s-1) f3=(f2>f1+b[j][0])?f2:f1+b[j][0];
				 s1+=f1+k1*b[j][0];//累加每次作業(yè)的完成時間
			 }
		for(j=0;j<n;j++)//計算s2的值（機器2沒有空閑的下界）
		 if(!y[j][1])   
		 {  
			 k2--;
			s1+=b[j][1];//s1的值
			s2+=f3+k2*b[j][1];//累加每次作業(yè)的完成時間 
		 }  
		return sf2+((s1>s2)?s1:s2);//返回完成時間和下界
 }

 
 void flowshop::bbflow(void)
 {  
	 int i;//循環(huán)控制變量
	 sort();//對各作業(yè)在每機器上的完成時間進(jìn)行排序
	 minheap h(1000000);//創(chuàng)建大小為1000000的堆
	 minheapnode e;//創(chuàng)建堆結(jié)點對象
	 e.init(n);//初始化
	 
	 while(e.s<=n) //搜索排列空間樹
	 {    
		 if(e.s==n)//已到葉結(jié)點結(jié)束
		 {       
			 if(e.sf2<bestc)//比當(dāng)前最優(yōu)值更小則更新
			 {        
				 bestc=e.sf2;//更新最優(yōu)值
				 for(i=0;i<n;i++)//設(shè)置最優(yōu)解
					 bestx[i]=e.x[i];
			 }
			 delete [] e.x;
		 }    
		 else{//否則繼續(xù)擴展結(jié)點
			 for(i=e.s;i<n;i++)
				{        
				 swap(e.x[e.s],e.x[i]);//考慮各種排列情況
				 int f1,f2;
				 int bb=bound(e,f1,f2,y);//計算下界
				 if(bb<bestc)//下界未超過最優(yōu)值，則子樹可能含最優(yōu)解
					{          
					 minheapnode N;//分配一個堆結(jié)點
					 N.newnode(e,f1,f2,bb,n);//給結(jié)點賦值
					 h.insert(N);//將結(jié)點插入堆
					}
				 swap(e.x[e.s],e.x[i]);//還原為原來的排列
				}
			 delete [] e.x;
		 }
			 if(!h.removemin(e)) break;//堆不為空，取下一擴展結(jié)點，否則退出循環(huán)
		}
 }


 flowshop::flowshop()
 {  
	 int i,j;//循環(huán)控制變量
	 ifstream fin("input.txt",ios::nocreate);//打開輸入文件
	 fin>>n;//讀入作業(yè)個數(shù)
	 if(!(m=new int*[n]))//分配二維數(shù)組m
	 {    
		 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		 exit(-1);
	 }  
		for(i=0;i<n;i++)    
			if(!(m[i]=new int[2]))//為每個一維數(shù)組分配空間
			{      
			 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			 delete[] m;
			 exit(-1);
			}  
	if(!(b=new int*[n]))//分配二維數(shù)組b
	{    
		cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		exit(-1);
	}  
		for(i=0;i<n;i++)
			 if(!(b[i]=new int[2]))//為每個一維數(shù)組分配空間
			 {     
				 cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				 delete[] b;
				 exit(-1);
			 } 
	if(!(a=new int*[n]))//分配二維數(shù)組a
	{    
		cerr<<"insufficient memory!"<<endl;//分配不成功，退出
		exit(-1);
	}  
		for(i=0;i<n;i++)
			if(!(a[i]=new int[2]))//為每個一維數(shù)組分配空間
			{      
				cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				delete[] a;
				exit(-1);
			}  
	if(!(y=new bool *[n]))//分配二維數(shù)組y
		{    
			cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			exit(-1);
		}  
		  for(i=0;i<n;i++)
			  if(!(y[i]=new bool[2]))//為每個一維數(shù)組分配空間
			  {      
				  cerr<<"insufficient memory!"<<endl;//分配不成功，退出
				  delete[] y;
				  exit(-1);
			  }  
	if(!(bestx=new int[n]))//分配bestx數(shù)組
		{    
			cerr<<"insufficient memory!"<<endl;//分配不成功，退出
			exit(-1);
		}  
	for(i=0;i<n;i++)
		for(j=0;j<2;j++)
			fin>>m[i][j];//讀入各個作業(yè)處理時間
	fin.close();//關(guān)閉輸入文件
	bestc=32767;//設(shè)定bestc初始值
 }

void flowshop::outputtofile()
	{
 	 int i;//循環(huán)控制變量	
	ofstream out("output.txt");//創(chuàng)建輸出文件
	 out<<bestc<<endl;//輸出最小完成時間和
	 for(i=0;i<n;i++)
	 {    
		 out<<bestx[i]+1<<" ";//輸出最優(yōu)解信息
	 }  
	 out.close();//關(guān)閉輸出文件


	 delete[] bestx;//釋放bestx所占內(nèi)存
	 for(i=0;i<n;i++)//釋放二維m數(shù)組所占內(nèi)存
		 delete[] m[i];
	 delete[] m;
	 for(i=0;i<n;i++)//釋放二維b數(shù)組所占內(nèi)存
		 delete[] b[i];
	 delete[] b;
	 for(i=0;i<n;i++)//釋放二維a數(shù)組所占內(nèi)存
		 delete[] a[i];
	 delete[] a;
	 for(i=0;i<n;i++)//釋放二維y數(shù)組所占內(nèi)存
		 delete[] y[i];
	 delete[] y;
 }
 


void main(void)
{
	flowshop flow;//創(chuàng)建flowshop對象
	flow.bbflow();//進(jìn)行調(diào)度求最優(yōu)解
	flow.outputtofile();//輸出最優(yōu)解
}