DLX板子（struct）

本文主要是介绍DLX板子（struct），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

仿照刘汝佳的板子写的OI用板子
与工程代码还是格格不入的
仅供学习参考

template <int node_num> struct DLX {int cn, nn; //col_num, node_numint S[node_num]; //node_num in a col, it wastes memint ansd, ans[node_num]; //it also wastes mem//node infoint row[node_num], col[node_num];int L[node_num], R[node_num], U[node_num], D[node_num];void init(int col_n) {cn = col_n;for(int i = 0;i <= cn;i++) {U[i] = D[i] = i;L[i] = i - 1; R[i] = i + 1;} L[0] = cn; R[cn] = 0; //turn to circlenn = cn + 1;memset(S, 0, sizeof(S));}void addrow(int r, int a[], int n) {int pre = nn;for(int i = 0;i < n;i++) {int c = a[i];D[nn] = c; U[nn] = U[c];L[nn] = nn - 1; R[nn] = nn + 1;D[U[c]] = nn; U[c] = nn;row[nn] = r; col[nn] = c;S[c]++; nn++;} L[pre] = nn - 1; R[nn - 1] = pre;}#define FOR(i, A, x) for(int i = A[x];i != x;i = A[i])void remove(int c) {L[R[c]] = L[c]; R[L[c]] = R[c];FOR(i, D, c)FOR(j, R, i) {U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--;}}void restore(int c) {FOR(i, U, c)FOR(j, L, i) {U[D[j]] = D[U[j]] = j;S[col[j]]++;}L[R[c]] = R[L[c]] = c;}inline bool end(int d) {//to rewritereturn R[0] == 0;} bool dfs(int d) {if(end(d)) {ansd = d;return 1;}int c = R[0];FOR(i, R, 0) if(S[i] < S[c]) c = i;remove(c);FOR(i, D, c) {ans[d] = row[i];FOR(j, R, i) remove(col[j]);if(dfs(d + 1)) return 1;FOR(j, L, i) restore(col[j]);}restore(c);return 0;}bool solve() { return dfs(0); }#undef FORDLX (int col_num) { init(col_num); }
};

这篇关于DLX板子（struct）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---