求助 DLX,#17-#10 TLE
查看原帖
求助 DLX,#17-#10 TLE
448887
cancan123456楼主2022/4/22 12:46
#include <cstdio>
using namespace std;
const int N = 505;
const int M = 6005;
int n, m;
int a[N][N];
int row[M], col[M];
int up[M], down[M], left[M], right[M];
int head, row_head[N];
int col_cnt[N];
int cnt;
void init() {
	cnt = m;
	head = 0;
	for (int i = 0; i <= m; i++) {
		up[i] = down[i] = i;
		col_cnt[i] = 0;
		left[i] = i - 1;
		right[i] = i + 1;
	}
	left[head] = m;
	right[m] = head;
	for (int i = 1; i <= n; i++) {
		row_head[i] = -1;
	}
}
void insert(int i, int j) {
	int now = ++cnt;
	col_cnt[j]++;
	row[now] = i;
	col[now] = j;
	up[now] = up[j];
	down[now] = j;
	up[down[now]] = down[up[now]] = now;
	if (row_head[i] == -1) {
		row_head[i] = now;
		left[now] = right[now] = now;
	} else {
		left[now] = row_head[i];
		right[now] = right[row_head[i]];
		left[right[row_head[i]]] = now;
		right[row_head[i]] = now;
	}
}
void build() {
	init();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 1) {
				insert(i, j);
			}
		}
	}
}
void remove(int del_col) {
	left[right[del_col]] = left[del_col];
	right[left[del_col]] = right[del_col];
	for (int i = down[del_col]; i != del_col; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = up[j];
			down[up[j]] = down[j];
			col_cnt[col[j]]--;
		}
	}
}
void recover(int del_col) {
	for (int i = down[del_col]; i != del_col; i = down[i]) {
		for (int j = right[i]; j != i; j = right[j]) {
			up[down[j]] = down[up[j]] = j;
		}
	}
	left[right[del_col]] = right[left[del_col]] = del_col;
}
int ans, ansk[N];
bool X() {
	if (right[head] == head) {
		return true;
	}
	int c = right[head];
	for (int i = right[head]; i != head; i = right[i]) {
		if (col_cnt[i] < col_cnt[c]) {
			c = i;
		}
	}
	remove(c);
	for (int i = down[c]; i != c; i = down[i]) {
		ansk[++ans] = row[i];
		for (int j = right[i]; j != i; j = right[j]) {
			remove(col[j]);
		}
		if (X()) {
			return true;
		}
		for (int j = left[i]; j != i; j = left[j]) {
			recover(col[j]);
		}
		ans--;
	}
	recover(c);
	return false;
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", a[i] + j);
		}
	}
	build();
	if (X()) {
		for (int i = 1; i <= ans; i++) {
			printf("%d ", ansk[i]);
		}
	} else {
		printf("No Solution!");
	}
	return 0;
}
2022/4/22 12:46
加载中...