2 条题解
-
0
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 5505; // 1的个数5000+列表头500 int n, m, cnt; // 矩阵的长,宽,点的编号 int u[N], d[N], l[N], r[N]; // 每个点的上下左右 int row[N], col[N]; // 每个点所在行,列 int h[N]; // 每行的头结点 int s[N]; // 每列的节点数 int ans[N]; // 选了哪些行 void init() { // 初始化第0行的列表头 for (int y = 0; y <= m; y++) { u[y] = d[y] = y; l[y] = y - 1; r[y] = y + 1; } l[0] = m; r[m] = 0; cnt = m; } void link(int x, int y) { // 在x行y列插入点 row[++cnt] = x; col[cnt] = y; s[y]++; u[cnt] = u[y]; // y...u[y]←→cnt←→y d[u[y]] = cnt; d[cnt] = y; u[y] = cnt; if (h[x] == 0) h[x] = r[cnt] = l[cnt] = cnt; // x行无点 else { l[cnt] = l[h[x]]; // h[x]...l[h[x]]←→cnt←→h[x] r[l[h[x]]] = cnt; r[cnt] = h[x]; l[h[x]] = cnt; } } void remove(int y) { // 删除y列与关联行 r[l[y]] = r[y], l[r[y]] = l[y]; for (int i = d[y]; i != y; i = d[i]) // 向下 for (int j = r[i]; j != i; j = r[j]) // 向右 u[d[j]] = u[j], d[u[j]] = d[j], s[col[j]]--; } void resume(int y) { // 恢复y列与关联行 r[l[y]] = y, l[r[y]] = y; for (int i = u[y]; i != y; i = u[i]) // 向上 for (int j = l[i]; j != i; j = l[j]) // 向左 u[d[j]] = j, d[u[j]] = j, s[col[j]]++; } bool dance(int dep) { // 在十字链表上跳舞 if (r[0] == 0) { for (int i = 0; i < dep; i++) printf("%d ", ans[i]); return True; } int y = r[0]; // 找出1的个数最少的列 for (int i = r[0]; i; i = r[i]) if (s[i] < s[y]) y = i; remove(y); for (int i = d[y]; i != y; i = d[i]) { ans[dep] = row[i]; for (int j = r[i]; j != i; j = r[j]) remove(col[j]); if (dance(dep + 1)) return True; for (int j = l[i]; j != i; j = l[j]) resume(col[j]); } resume(y); return False; } int main() { scanf("%d%d", &n, &m); init(); for (int i = 1; i <= n; i++) for (int j = 1, x; j <= m; j++) if (scanf("%d", &x), x) link(i, j); if (!dance(0)) puts("No Solution!"); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:59:15
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 5505; // 1的个数5000+列表头500 int n, m, cnt; // 矩阵的长,宽,点的编号 int u[N], d[N], l[N], r[N]; // 每个点的上下左右 int row[N], col[N]; // 每个点所在行,列 int h[N]; // 每行的头结点 int s[N]; // 每列的节点数 int ans[N]; // 选了哪些行 void init() { // 初始化第0行的列表头 for (int y = 0; y <= m; y++) { u[y] = d[y] = y; l[y] = y - 1; r[y] = y + 1; } l[0] = m; r[m] = 0; cnt = m; } void link(int x, int y) { // 在x行y列插入点 row[++cnt] = x; col[cnt] = y; s[y]++; u[cnt] = u[y]; // y...u[y]←→cnt←→y d[u[y]] = cnt; d[cnt] = y; u[y] = cnt; if (h[x] == 0) h[x] = r[cnt] = l[cnt] = cnt; // x行无点 else { l[cnt] = l[h[x]]; // h[x]...l[h[x]]←→cnt←→h[x] r[l[h[x]]] = cnt; r[cnt] = h[x]; l[h[x]] = cnt; } } void remove(int y) { // 删除y列与关联行 r[l[y]] = r[y], l[r[y]] = l[y]; for (int i = d[y]; i != y; i = d[i]) // 向下 for (int j = r[i]; j != i; j = r[j]) // 向右 u[d[j]] = u[j], d[u[j]] = d[j], s[col[j]]--; } void resume(int y) { // 恢复y列与关联行 r[l[y]] = y, l[r[y]] = y; for (int i = u[y]; i != y; i = u[i]) // 向上 for (int j = l[i]; j != i; j = l[j]) // 向左 u[d[j]] = j, d[u[j]] = j, s[col[j]]++; } bool dance(int dep) { // 在十字链表上跳舞 if (r[0] == 0) { for (int i = 0; i < dep; i++) printf("%d ", ans[i]); return True; } int y = r[0]; // 找出1的个数最少的列 for (int i = r[0]; i; i = r[i]) if (s[i] < s[y]) y = i; remove(y); for (int i = d[y]; i != y; i = d[i]) { ans[dep] = row[i]; for (int j = r[i]; j != i; j = r[j]) remove(col[j]); if (dance(dep + 1)) return True; for (int j = l[i]; j != i; j = l[j]) resume(col[j]); } resume(y); return False; } int main() { scanf("%d%d", &n, &m); init(); for (int i = 1; i <= n; i++) for (int j = 1, x; j <= m; j++) if (scanf("%d", &x), x) link(i, j); if (!dance(0)) puts("No Solution!"); return 0; }
- 1
