电路板排列问题
class BoardNode {
friend int BBArrangement(int **, int, int, int* &);
public:
operator int() const { return cd; }
private:
int *x, s, cd, *now;
};
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];
for (int i = 1; i <= m; i++)
total[i] = 0;
E.now[i] = 0;
for (int i = 1; i <= n; i++) {
E.x[i] = i;
for (int j = 1; j <= m; j++) {
total[j] += B[i][j];
}
}
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 (int j = 1; j <= m; j++)
if (N.now[j] > 0 && total[j] != N.now[j])
ld++;
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];
N.x[N.s] = E.x[i];
N.x[i] = E.x[N.s];
H.Insert(N);
} else {
delete[] N.now;
}
delete[] E.x;
}
try {
H.DeleteMin(E);
} catch (OutOfBounds) {
return bestd;
}
}
} while (E.cd < bestd);
do {
delete[] E.x;
delete[] E.now;
try {
H.DeleteMin(E);
} catch (...) {
break;
}
} while(true);
return bestd;
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42