#include<iostream>
using namespace std;

/*
設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入電路板x[i]
x所確定的電路板排列密度density(x)定義為跨越相鄰電路板插槽的最大連接數
在設計機箱，插槽一側的布線間隙由電路板排列的密度所確定
因此電路板排列問題要求對于給定電路板連接條件（連接塊），確定電路板的最佳排列，使
其具有最小的密度
    算法中用整型數組B表示輸入。B[i][j]的值為1當且僅當電路板i在連接塊Nj中。設
total[j]是連接塊Nj中的電路板數。對于電路板的部分排列x[1:i]，設now[j]是x[1:i]中所
包含的Nj中的電路板數。由此可知，連接塊Nj的連線跨越插槽i和i+1當且僅當now[j]》0
且now[j]!=total[j]。我們可以利用這個條件來計算插槽i和插槽i+1之間的連線密度。

電路板排列問題的解空間樹是一棵排列樹。我們采用優先隊列式分支限界法找出
所給的電路板的最小密度布局。算法中用一個最小堆來表示活結點優先隊列。
最小堆中元素類型是BoardNode。每一個BoardNode類型的結點包含域x，用來表示
結點所相應的電路板排列；s表示該結點已確定的電路板排列x[1:s];cd表示當前密度
;now[j]表示x[1:s]中所含連接塊j中的電路板數。具體算法描述如下：
*/

class BoardNode
{
	friend int BBArrangement( int**, int, int, int* & );
public:
	operator int() const
	{
		return cd;
	}
	bool operator>( const BoardNode& a ) const
	{
		return cd > a.cd;
	}

	bool operator<( const BoardNode& a ) const
	{
		return cd < a.cd;
	}
private:
	int *x;
	//x[1:n]記錄電路板排列
	int s;
	//x[1:s]是當前結點所相應的部分排列
	int cd;
	//x[1:s]的密度
	int* now;
	//now[j]是x[1:s]所含連接塊j中電路板數目
};

/*
函數BBArrangement是解電路板排列問題的優先隊列式分支限界法的主體。
算法開始的時候，將排列樹的根結點置為當前擴展結點。
在初始擴展結點處還沒有
選定電路板，故s=0,cd=0,now[i]=0,1<=i<=n。且數組x初始化為單位排列。數組total
初始化為total[i],等于連接塊i所含電路板數目。bestd表示當前最小密度，bestx是
相應的最優解。
算法的do-while循環完成對排列樹內部結點的有序擴展。在do-while循環體內算法依次從
活結點優先隊列中取出具有最小cd值的結點作為當前擴展結點，并加以擴展。
如果當前擴展結點的cd>=bestd,則優先隊列中其余活結點都不可能導致最優解，
此時算法結束。
算法將當前擴展結點分為兩種情形處理。首先考慮s=n-1的情形，此時已排定n-1塊
電路板，故當前擴展結點是排列樹中的一個葉結點的父結點。x表示相應于該葉結點的電路板
排列。計算出與x相應的密度并在必要時更新當前最優值bestd和相應的當前最優解bestx。
當s<n-1時，算法依次產生當前擴展結點的所有兒子結點。對于當前擴展結點的每一個
兒子結點N，計算出其相應的密度N.cd。當n.cd<bestd時，將該兒子結點N插入到活結點
優先隊列中。而當N.cd>=bestd時，以N為根的子樹中不可能有比當前最優解bestx更好的
解，故可將結點N舍去。
*/

template<class Type>
class MinHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MinHeap(int n)
		{
			H = NULL;
			H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			Capacity = n;
			Size = 0;
		}
		MinHeap( MinHeap& a )
		{
			//要排除自賦值的情況
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		}

		/*
		基本的堆插入操作
		為了將node插入到堆中
		首先在下一個空閑位置++Size處，創建一個空穴，否則該堆將不是完全樹
		如果x可以放在該穴中而不破壞堆的序，那么插入完成
		否則我們把空穴的父親結點上的元素移動到該穴中，這樣空穴就朝著根的方向上行一步
		繼續該過程直到x能被放入空穴為止
		*/
		void Insert( Type& node )
		{
			int i;
			cout<<"Size = "<<Size<<endl;
			for( i = ++Size; H[i / 2] > node; i /= 2 )
			{
				H[i] = H[i / 2];
				if ( i / 2 == 0 )
				{
					break;
				}
			}
			H[i] = node;
			
		}

		/*
		當刪除一個最小元時
		在根結點處產生一個空穴。
		由于現在堆少了一個元素，因此堆中最后一個元素必須移動到該堆的某個地方
		如果x可以放到空穴中，那么DeleteMin完成
		否則應該將兩個兒子中較小者移入空穴
		這樣空穴就向下推了一層。重復該步驟直到x可以被放入空穴中
		*/
		void DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			MinElement = H[ 1 ];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] < H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement > H[ Child ] )
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			H[i] = LastElement;
			node = MinElement;
		}
};

int max( int a, int b )
{
	int maxint = 0;
	maxint = a > b ? a : b;
	return maxint;
}

int BBArrangement( int** B, int n, int m, int* &bestx )
{
	//解電路板排列問題的優先
	MinHeap< BoardNode > H(1000);
	//活結點最小堆
	BoardNode E;
	E.x = new int[n+1];
	E.s = 0;
	E.cd = 0;
	E.now = new int[m+1];
	int *total = new int[m+1];
	//now[i] = x[1:s]所含連接塊i中電路板數
	//total[i]=連接塊i中電路板數
	for( int i = 1; i <= m; ++i )
	{
		total[i] = 0;
		E.now[i] = 0;
	}

	for( i = 1; i <= n; ++i )
	{
		E.x[i] = i;
		//初始排列為12345...n
		for( int j = 1; j <= m; ++j )
		{
			total[j] += B[i][j];
			//連接塊j中電路板數
			//初始花的時候，如果i在j塊，就有B[i][j]=1，所以這里可以做好判定
		}
	}

	int bestd = m + 1;
	//當前最小密度
	bestx = 0;
	//首先初始化一個最小密度結點

	do
	{
		//結點擴展
		if ( E.s == n - 1 )
		{
			//僅一個兒子結點
			int ld = 0;
			//最后一塊電路板的密度
			for( int j = 1; j <= m; ++j )
			{
				ld += B[E.x[n]][j];
			}
			//看最后一個結點的密度大小

			if ( ld < bestd )
			{
				//如果最后一個增加后的密度小于獲得的最小密度，則求出結果如果大于
				delete []bestx;
				bestx = E.x;
				bestd = max( ld, E.cd );
				//一個組合的最小密度求出，下才不斷的找比他小的密度
			}
			else
			{
				//delete []E.x;
			}
			//delete []E.now;
		}
		else
		{
			//產生當前擴展結點的所有兒子結點
			for( int i = E.s + 1; i <= n; ++i )
			{
				BoardNode N;
				N.now = new int[m+1];
				for( int j = 1; j <= m; ++j )
				{
					//新插入的電路板
					N.now[j] = E.now[j] + B[E.x[i]][j];
				}
				int ld = 0;
				//新插入電路板的密度
				for( j = 1; j <= m; ++j )
				{
					if ( N.now[j] > 0 && total[j] != N.now[j] )
					{
						ld++;
					}
					//說明當前結點下還有和其他結點的交叉，也就是密度要加1
				}
				N.cd = max( ld, E.cd );
				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];
					}
					//初始化新結點，利用E結點進行初始化，將E結點中所選擇的
					//所有的結點進行初始化
					N.x[N.s] = E.x[i];
					//先確定N.s結點是哪個
					N.x[i] = E.x[N.s];
					//然后要確定第i個結點應該是
					//實際是實現了兩個結點的交換，因為是全排列
					//i,N.s交換信息

					H.Insert( N );
				}
				else
				{
					delete []N.now;
				}
			}
			//delete []E.x;
			//完成當前結點擴展
		}

		/*try
		{
			H.DeleteMin(E);
			//取下一個擴展結點
		}
		catch(OutOfBounds)
		{
			return bestd;
			//無擴展結點
		}*/
		if ( H.Size == 0 )
		{
			return bestd;
		}
		else
		{
			H.DeleteMin(E);
			//取下一個擴展結點
		}
	}
	while(E.cd < bestd );

	//釋放最小堆中所有結點
	do
	{
		//delete []E.x;
		//delete []E.now;
		try
		{
			H.DeleteMin(E);
		}
		catch(...)
		{
			break;
		}
	}while(true);

	cout<<"bestd is : "<<bestd<<endl;

	return bestd;
}

int main()
{
	int **B = 0;
	B = new int*[9];
	if ( 0 == B )
	{
		return -1;
	}
	for( int i = 0; i < 9; ++ i )
	{
		B[i] = 0;
		B[i] = new int[6];
		if ( 0 == B[i] )
		{
			return -1;
		}
		for( int j = 0; j < 6; ++j )
		{
			B[i][j] = 0;
		}
	}

	B[4][1] = 1;
	B[5][1] = 1;
	B[6][1] = 1;

	B[2][2] = 1;
	B[3][2] = 1;

	B[1][3] = 1;
	B[3][3] = 1;

	B[3][4] = 1;
	B[6][4] = 1;

	B[7][5] = 1;
	B[8][5] = 1;

	int n = 8;
	int m = 5;

	int *bestx = new int[9];
	for( int s = 0; s < 9; ++s )
	{
		for( int s1 = 0; s1 < 6; ++s1 )
		{
			cout<<B[s][s1]<<" ";
		}
		cout<<endl;
	}
	//Arrangement( B, n, m, bestx );
	BBArrangement( B, n, m, bestx );
	
	return 0;
}