#include <**iostream**>
#include <**fstream**>
#include <**algorithm**>
#include <**functional**>
#include <**queue**>
using namespace std;
class BoardNode{
public:
int *x;//x[1:n]记录电路板排列
int n;
int t;//x[1:t]是当前节点所相应的部分排列
int maxL;//x[1:s]的最大长度
BoardNode(){};
BoardNode(BoardNode const &source){
n = source.n;
t = source.t;
maxL = source.maxL;
x = new int[n + 1];
for (int i = 0; i <= n; ++i)
x[i] = source.x[i];
}
bool Comput(int i,int m,int **B);//计算本块所形成的排列maxL
bool operator < (const BoardNode &A)const{
if (this->t > A.t)
return true;
else if(this->t == A.t){
return this->maxL < A.maxL ? true : false;
}
else
return false;
}
};
bool BoardNode::Comput(int i,int m,int **B){
++this->t;
swap(x[t],x[i]);
int *low = new int[m + 1];
int *high = new int[m + 1];
for (int j = 0; j <= m; ++j){
low[j] = m;
high[j] = 0;
}
for (j = 1; j <= t; ++j){
for (int k = 1; k <= m; ++k){
if (B[x[j]][k]){
if (j < low[k])
low[k] = j;
if (j > high[k])
high[k] = j;
}
}
}
maxL = 0;
for (j = 1; j <=t ;++j){
if (maxL < high[j] - low[j])
maxL = high[j] - low[j];
}
delete low;
delete high;
return true;
}
//////////////////////////////////
class minBorad{
private:
int **B;//描述矩阵
int n;//n块电路板
int m;//m个连接块
int *bestx;//bestx[1:n]最优排列
int bestMaxL;//最优最大长度
BoardNode E;
priority_queue Heap;
void BBArrangement();
void cmpBest(BoardNode &newBoardNode);
public:
minBorad(){};
minBorad(int **B, int n, int m){
this->B = B;
this->n = n;
this->m = m;
bestx = new int[n + 1];
bestMaxL = INT_MAX;
E.x = new int[n + 1];
E.maxL = 0;
E.n = n;
E.t = 0;
for (int i = 0; i <= n; ++i)
{
E.x[i] = i;
}
BBArrangement();
}
int getBestMaxL(){return this->bestMaxL;}
int *getBestx(){return this->bestx;}
};
void minBorad::cmpBest(BoardNode &newBoardNode){
if (newBoardNode.maxL <= this->bestMaxL)
{
this->bestMaxL = newBoardNode.maxL;
cout<<"当前最优："<
for (int i = 0; i
{
this->bestx[i] = newBoardNode.x[i];
cout<<bestx[i]<<" ";
}
cout<<endl;
}
}
void minBorad::BBArrangement(){
Heap.push(E);
while(!Heap.empty()){
BoardNode nowNode(Heap.top());
Heap.pop();
// cout<<"弹出节点 "<<nowNode.t<<endl;
// for (int z = 0; z <= n; ++z)
// {
// cout<<nowNode.x[z]<<" ";
// }
// cout<<endl;
for (int i = nowNode.t + 1; i <= n; ++i)
{
BoardNode newBoardNode(nowNode);
newBoardNode.Comput(i,m,B);
if (newBoardNode.maxL < bestMaxL)//如果当前最大长度小于最优长度则搜索子树
{
if (newBoardNode.t == n)
{
cmpBest(newBoardNode);
}
else{
Heap.push(newBoardNode);
// cout<<"加入节点 "<<newBoardNode.t<<endl;
// for (int z = 0; z <= n; ++z)
// {
// cout<<newBoardNode.x[z]<<" ";
// }
// cout<<endl;
}
}
}
}
};
int main(){
ifstream in("input.txt");
ofstream out("output.txt");
//#define in cin
//#define out cout
int cases;
in>>cases;
for(int Case = 1; Case <= cases; ++Case){
int n,m;
in>>n>>m;
int **B = new int *[n + 1];
int i,j;
for (i = 1; i <= n; ++i)
{
B[i] = new int [m];
}
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m; ++j)
{
in>>B[i][j];
}
}
minBorad cmpMinBorad(B,n,m);
out<<"Case #"<<Case<<": "<<cmpMinBorad.getBestMaxL()<<endl;
for (j = 1; j <= n; ++j)
{
out<<(cmpMinBorad.getBestx())[j]<<" ";
}
out<<endl;
}
return 0;
}
input问文本输入
8 5
11111
01010
01110
10110
10100
11010
00001
01001
output输出的结果不对为什么啊？？？还有算法复杂度是多少啊？怎么算的
