林晓佳-5.5分.txt

这是很不错的计算机算法

#include <fstream>
#include "iostream.h"
#include <iomanip>
using namespace std;

int size;
class flowshop;

class minheapnode
{
  friend flowshop;
  public:
    int bb; 
    minheapnode();
    minheapnode(minheapnode& temp); 
    minheapnode& operator = (minheapnode& temp);
    ~minheapnode();
  private:
    int s;
    int f1;
    int f2; 
    int sf2; 
    int *x;
    void newnode(minheapnode,int,int,int,int); 
};


minheapnode::minheapnode()
{
  x=new int[size];
  for(int i=0;i<size;i++) x[i]=i; 
  s=f1=f2=sf2=bb=0;
}


minheapnode::minheapnode(minheapnode& temp)
{
  s=temp.s;
  f1=temp.f1;
  f2=temp.f2;
  sf2=temp.sf2;
  bb=temp.bb;
  x=new int[size]; 
  for(int i=0;i<size;i++) x[i]=temp.x[i];
}


minheapnode& minheapnode::operator = (minheapnode& temp)
{
  s=temp.s;
  f1=temp.f1;
  f2=temp.f2;
  sf2=temp.sf2;
  bb=temp.bb; 
  for(int i=0;i<size;i++) x[i]=temp.x[i]; 
  return *this; 
}


minheapnode::~minheapnode()
{
  delete[] x; 
}


void minheapnode::newnode(minheapnode e,int ef1,int ef2,int ebb,int n)
{
  x=new int[n];//分配x数组 
  for(int i=0;i<n;i++) x[i]=e.x[i];//x数组赋值 
  f1=ef1;
  f2=ef2;
  sf2=e.sf2+f2;
  bb=ebb;
  s=e.s+1;
}



class minheap  
{
public:
	makeempty();
	int isfull();
	int isempty();
	int removemin(minheapnode& x);
	int insert(minheapnode& x);
	minheap(int n);
	minheap();
	virtual ~minheap();
private:
	 minheapnode *heap;
	 int currentsize; 
	 int heapsize; 
	 void filterdown(int start,int endofheap); 
	 void filterup(int start);

};
minheap::minheap()
{

}

minheap::~minheap()
{
	delete[] heap;
}

minheap::minheap(int n)
{
	heapsize=n;
  currentsize=0; 
  if(!(heap=new minheapnode[heapsize]))
  {
   return;
  }

}

int minheap::insert(minheapnode &x)
{
	if(currentsize==heapsize)//堆已满不能插入 
  {
    cout<<"堆已满"<<endl;
    return 0;
  }	
  heap[currentsize]=x;//在堆尾插入元素 
  filterup(currentsize);//向上调整为最小堆 
  currentsize++;//元素个数加1 
  return 1;
}

int minheap::removemin(minheapnode &x)
{
	if(!currentsize)//堆空不能删除 
  { 
    cout<<"堆已空"<<endl;
    return 0; 
  }
  x=heap[0];//堆首元素赋给x 
  heap[0]=heap[currentsize-1];//堆尾元素移动到堆首	    
  currentsize--;//元素个数减1 
  filterdown(0,currentsize-1);//向下调整为最小堆 
  return 1;
}

int minheap::isempty()
{
	return currentsize==0;
}

int minheap::isfull()
{
	return currentsize==heapsize;
}

minheap::makeempty()
{
	currentsize=0;
}
void minheap::filterdown(int start,int endofheap)
{
  int i=start,j=2*i+1; 
  minheapnode temp=heap[i]; 
  while(j<=endofheap)
  {
    if(j<endofheap&&heap[j].bb>heap[j+1].bb) j++;
    if(temp.bb<=heap[j].bb) break; 
    else 
    {
      heap[i]=heap[j];
      i=j;
      j=2*j+1;
    }
  }
  heap[i]=temp; 
}
void minheap::filterup(int start)
{
  int j=start,i=(j-1)/2;
  minheapnode temp=heap[j];
  while(j>0)
  {
    if(heap[i].bb<temp.bb) break;
    else
    {
      heap[j]=heap[i];
      j=i;
      i=(i-1)/2; 
    }
  }
  heap[j]=temp; 
}



class flowshop  
{
public:
	void sort();
	int bound(minheapnode e,int& f1,int& f2,int **y);
	void outputfile();
	void bbflow();
	flowshop();
	virtual ~flowshop();
private:
	int n;
	int **m;
	int **b;
	int **a; 
	int *bestx;
	int bestc;
	int **y; 
};
flowshop::flowshop()
{
	std::ifstream i_file("input.txt");
	if(!i_file.is_open())
		return;
	i_file>>n;
	size=n;
	if(!(m=new int*[n]))
		return;
	for(int i=0;i<n;i++)
    if(!(m[i]=new int[2]))
    {
      delete[] m;
      return;
    }
		if(!(b=new int*[n])) 
		{
			return;
		}
		for(i=0;i<n;i++)
			if(!(b[i]=new int[2]))
			{
				delete[] b;
				return;
			}
			if(!(a=new int*[n]))
			{
				return;
			}
			for(i=0;i<n;i++)
				if(!(a[i]=new int[2]))
				{
					delete[] a;
					return;
				}
				if(!(y=new int*[n]))
				{
					return;
				}
				for(i=0;i<n;i++)
					if(!(y[i]=new int[2]))
					{
						delete[] y;
						return;
					}
					if(!(bestx=new int[n]))
					{
						return;
					}
					for(i=0;i<n;i++)
						for(int j=0;j<2;j++)
							i_file>>m[i][j];
						
						bestc=10000;
	

}

flowshop::~flowshop()
{
	delete[] bestx;
  for(int i=0;i<n;i++) 
    delete[] m[i];
  delete[] m;
  for(i=0;i<n;i++) 
    delete[] b[i];
  delete[] b;
  for(i=0;i<n;i++)
    delete[] a[i];
  delete[] a;
  for(i=0;i<n;i++)
    delete[] y[i];
  delete[] y;

}

void flowshop::bbflow()
{
	sort();
  minheap h(100000); 
  minheapnode e;
  while(e.s<=n)
  {
    if(e.s==n)
    { 
      if(e.sf2<bestc)
      {
        bestc=e.sf2; 
        for(int i=0;i<n;i++)
          bestx[i]=e.x[i];
      }
     
    }
    else
      for(int 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)
        {
          minheapnode N;
          N.newnode(e,f1,f2,bb,n); 
          h.insert(N);
        }
        swap(e.x[e.s],e.x[i]);
      }
			if(!h.removemin(e)) break;
  }

}

void flowshop::outputfile()
{
	std::ofstream o_file("output.txt");//创建输出文件
	o_file<<bestc<<endl;//输出最小完成时间和
	for(int i=0;i<n;i++)
  {
    o_file<<bestx[i]+1<<" ";//输出最优解信息 
  }

}

int flowshop::bound(minheapnode e, int &f1, int &f2, int **y)
{
	for(int k=0;k<n;k++)
    for(int j=0;j<2;j++)
      y[k][j]=0;
		for(k=0;k<=e.s;k++)
			for(int j=0;j<2;j++)
				y[a[e.x[k]][j]][j]=1;
			f1=e.f1+m[e.x[e.s]][0];
			f2=((f1>e.f2)?f1:e.f2)+m[e.x[e.s]][1];
			int sf2=e.sf2+f2;
			int s1=0,s2=0,k1=n-e.s,k2=n-e.s,f3=f2;
			for(int j=0;j<n;j++)
				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]; 
				}
				for(j=0;j<n;j++)
					if(!y[j][1])
					{
						k2--;
						s1+=b[j][1];
						s2+=f3+k2*b[j][1];
					}
					return sf2+((s1>s2)?s1:s2);

}

void flowshop::sort()
{
  int *c=NULL;
  if(!(c=new int[n]))
  {
    return;
  }
  for(int j=0;j<2;j++)
  {
    for(int i=0;i<n;i++)
    {
      b[i][j]=m[i][j];
      c[i]=i;
    }
    for(i=0;i<n-1;i++)//冒泡排序趟数 
      for(int 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;//设置m和b的关系数组a 
  }
  delete[] c;//释放c所占内存 

}

void main()
{
  flowshop flow;
  flow.bbflow(); 
  flow.outputfile();
}