![]() |
#2
灰渣2016-06-19 17:38
这里有部分,可是有问题啊,大神们顺便看看
class BoardNode{ friend int RBArrangeBoards(int **,int,int *&); public: operator int() const{return cd; } int len(int **,int ii); private: int *x,s,cd; }; int BoardNode::len(int **conn,int ii) { for(int j=i+1,sum=0;i<=ii;i++){ int dist=x[i]>x[j]? x[i]-x[j]:x[j]-x[i]; sum+=conn[i][j]*dist; } return sum; } int RBArrangeBoards (int **conn, int n, int *&bestx) { MinHeap<BoardNode>H(HeapSize) ; BoardNode E; E.x=new int[n+1]; E.s=0;E.cd=0; for(int i=l;i<=n;i++)E.x[i]=i int bestd=INT_MAX; bestx=0; while(E.cd<bestd){ if (E.S==n-1){ int ld=E.len(coon,n); if(ld<bestd){ delete[]bestx; bestx=E.x;bestd=ld; } elde{ for(int i=E.s+l;i<=n;i++){ BoardNode N; N.x=new int[n+l]; N.s=E.s+l; for (int j=l; j<=n;j++) N.x[j]=E.x[j]; N. x[N. s]=E. x[i]; N. x[i]=E. x[n.s]; N.cd=X.len(conn,N.s); if (N.cd<=bestd) H.Insert (N) ; else delete[]N. x ; } deletc[] E. x ; try {H. DeleteMin(E) ;} catch (OutOfBounds) (return bestd;} } while (true){ delete[] E.x; try(H.DeleteMin(E) ;} catch(...){ break;} } return bestd; } int main() { cin>>n; p=new int[n+l]; int **B; Make2DArray(B,n+1,nl+) ; for(lnt i=l;i<=n-1;i++) for (int j=i+1; j<=n; j++) cin>>[i][j] ; cout<<BBArrangeBoards (B, n, p)<< endl ; for (i=l;i<=n; i++) cout<<p[i]<<" "; cout<<endl; return O; } |
假设要将一组原件安装在线路板上,为此要设计一个线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和元件j之间的连线数为conn(i,j).如果将元件i安装在线路板上位置r处,而将元件j安装在s处则元件i和元件j之间的距离为dist(r,s)。确定了所给n个元件的安装位置,就确定了一个布线方案。与此布线方案对应的布线成本为。试设计一个优先队列式分支限界法,找出所给n个元件的布线成本最小的布线方案。
由文件input.txt给出输入数据。第一行有一个正整数N(1<=n<=20)。接下来的n-1行,每行n-i个数,表示元件i和元件j之间的连线数。1<=i<j<=20.
将计算出的结果输出到文件output.txt
输入文件示例
input.txt
3
2 3
3
输出文件示例
10
1 3 2
/////////下面有东西
[此贴子已经被作者于2016-6-19 17:39编辑过]