DLX hust 1017

“精确覆盖”问题

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;

const int max_size = 1005 * 105;
const int maxint = 0x3f3f3f3f;
int L[max_size], R[max_size], U[max_size], D[max_size], CH[max_size], RH[max_size];
int S[1005], O[1005];
int head, size;

void remove(const int &c) {
	//remove column c and all row i that A[i][c] == 1
	L[R[c]] = L[c];
	R[L[c]] = R[c];
	//remove column c;
	for (int i = D[c]; i != c; i = D[i]) {
	//remove i that A[i][c] == 1
		for (int j = R[i]; j != i; j = R[j]) {
			U[D[j]] = U[j];
			D[U[j]] = D[j];
			--S[CH[j]];
			//decrease the count of column C[j];
		}
	}
}
void resume(const int &c) {
	for (int i = U[c]; i != c; i = U[i]) {
		for (int j = L[i]; j != i; j = L[j]) {
			++S[CH[j]];
			U[D[j]] = j;
			D[U[j]] = j;
		}
	}
	L[R[c]] = c;
	R[L[c]] = c;
}
int len;
bool dfs(const int &k) {
	//cout << "new DFS" << endl;
	if (R[head] == head) {
		//One of the answers has been found.
		return true;
	}
	int s(maxint), c;
	//out(head);
	for (int t = R[head]; t != head; t = R[t]) {
		//out(t); out(R[t]);
		//select the column c which has the fewest number of element.
		if (S[t] < s) {
			s = S[t];
			c = t;
		}
	}
	//cout << "remove " << c << endl;
	remove(c);
	for (int i = D[c]; i != c; i = D[i]) {
		O[k] = i; //record the answer.
		len = k;
		for (int j = R[i]; j != i; j = R[j]) {
			remove(CH[j]);
		}
		if (dfs(k + 1)) {
			return true;
		}
		for (int j = L[i]; j != i; j = L[j]) {
			resume(CH[j]);
		}
	}
	resume(c);
	return false;
}
int node(int up, int down, int left, int right) {
	U[size] = up, D[size] = down;
	L[size] = left, R[size] = right;
	D[up] = U[down] = R[left] = L[right] = size;
	return size++;
}
void init(int M) {
	size = 0;
	head = node(0, 0, 0, 0);
	for (int j = 1; j <= M; ++j) {
		node(j, j, L[head], head);
		CH[j] = j, S[j] = 0;
	}
}

int main()
{
	int N, M, cnt;
	while (scanf("%d%d", &N, &M) != EOF)
	{
		init(M);
		for (int i = 1; i <= N; ++i) {
			scanf("%d", &cnt);
			int row = -1;
			while (cnt--) {
				int j;
				scanf("%d", &j);
				CH[size] = j, ++S[j];
				if (row == -1) {
					row = node(U[CH[j]], CH[j], size, size);
					RH[row] = i;
				} else {
					int k = node(U[CH[j]], CH[j], L[row], row);
					RH[k] = i;
				}
			}
		}
		//out("DFS");
		bool ans = dfs(1);
		if (ans) {
			printf("%d", len);
			for (int i = 1; i <= len; ++i)
				printf(" %d", RH[O[i]]);
			printf("\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}