SPOJ 1771&&DLX精确覆盖，重复覆盖

DLX的题，做过这题才算是会吧。

这道题转化成了精确覆盖模型来做，一开始，只是单纯的要覆盖完行列和斜线，WA。

后来醒悟了，不能这样，只要覆盖全部行或列即可。虽然如此，但某些细节地方很关键不能考虑到。

特别要注意的是

for(int i=R[c];i;i=R[i]){ if(i>ne) break; if(S[i] < S[c]) c = i;}

找最小值只能是在ne之前，为什么呢？因为我们要完全覆盖行。可行吗？可行。稍微留意一下DLX的模板就知道，它其实在选中一列之后，是会枚举列上的行值，

也就是说，该列（代表棋盘某一行）的每一个们置都会考虑到，不必担心无解。

DLX这个算法很巧妙啊，其实它只是一种高效的剪枝吧。妙妙妙，做过这题后才算真正懂得这个算法。

#include<cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int maxn=500;

const int maxnode=500*2500;

int ne;

int anst[maxn];

struct DLX

{

  int n , sz;                                                 // 行数，节点总数

  int S[maxn];                                                // 各列节点总数

  int row[maxnode],col[maxnode];                              // 各节点行列编号

  int L[maxnode],R[maxnode],U[maxnode],D[maxnode];            // 十字链表

  int ansd,ans[maxn];                                         // 解

  void init(int n )

  {

    this->n = n ;

    for(int i = 0 ; i <= n; i++ )

    {

      U[i] = i ;

      D[i] = i ;

      L[i] = i - 1;

      R[i] = i + 1;

    }

    R[n] = 0 ;

    L[0] = n;

    sz = n + 1 ;

    memset(S,0,sizeof(S));

  }

  void addRow(int r,vector<int> c1)

  {

    int first = sz;

    for(int i = 0 ; i < c1.size(); i++ ){

      int c = c1[i];

      L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c];

      D[U[c]] = sz; U[c] = sz;

      row[sz] = r; col[sz] = c;

      S[c] ++ ; sz ++ ;

    }

    R[sz - 1] = first ; L[first] = sz - 1;

  }

  // 顺着链表A，遍历除s外的其他元素

  #define FOR(i,A,s) for(int i = A[s]; i != s ; 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) {++S[col[j]];U[D[j]] = j;D[U[j]] = j; }

    L[R[c]] = c;

    R[L[c]] = c;

  }

  bool dfs(int d){

    if(d >= ne ){

      ansd=d;

      for(int i=0;i<ne;i++){

      	int x=(ans[i]-1)/ne+1;

      	int y=(ans[i]-1)%ne+1;

      	anst[x]=y;

      }

      printf("%d",anst[1]);

      for(int i=2;i<=ne;i++)

      printf(" %d",anst[i]);

      printf("\n");

      return true;

    }

    // 找S最小的列c

    int c = R[0] ;

    for(int i=R[c];i;i=R[i]){ if(i>ne) break; 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 true;

      FOR(j,L,i) restore(col[j]);

    }

    restore(c);

    return false;

  }

  void solve(){

    dfs(0);

  }

};

DLX solver;

int puzzle[100][100];

int main(){

	int tmp;

	while(scanf("%d",&ne)!=EOF){

		memset(puzzle,0,sizeof(puzzle));

		for(int k=1;k<=ne;k++){

			scanf("%d",&tmp);

			if(tmp>0){

				for(int i=1;i<=ne;i++)

				puzzle[k][i]=puzzle[i][tmp]=-1;

				for(int i=1;k-i>0&&tmp-i>0;i++)

				puzzle[k-i][tmp-i]=-1;

				for(int i=1;k+i<=ne&&tmp+i<=ne;i++)

				puzzle[k+i][tmp+i]=-1;

				for(int i=1;k-i>0&&tmp+i<=ne;i++)

				puzzle[k-i][tmp+i]=-1;

				for(int i=1;k+i<=ne&&tmp-i>0;i++)

				puzzle[k+i][tmp-i]=-1;

				puzzle[k][tmp]=1;

			}

		}

		solver.init(6*ne-2);

		vector<int>columns;

		for(int i=1;i<=ne;i++){

			for(int j=1;j<=ne;j++){

				columns.clear();

				if(puzzle[i][j]>=0){

					columns.push_back(i);

					columns.push_back(ne+j);

					columns.push_back(ne*2+j-1+i);

					columns.push_back(ne*2+2*ne-1+ne-i+j);

					solver.addRow((i-1)*ne+j,columns);

				}

			}

		}

		solver.solve();

	}

	return 0;

}

摘http://www.cnblogs.com/jh818012/p/3252154.html

重复覆盖模板

const int maxn=360000;

const int maxc=500;

const int maxr=500;

const int inf=0x3f3f3f3f;

int L[maxn], R[maxn], D[maxn], U[maxn], C[maxn];

int S[maxc], H[maxr], size;

///不需要S域

void Link(int r, int c)

{

    S[c]++; C[size]=c;

    U[size]=U[c]; D[U[c]]=size;

    D[size]=c; U[c]=size;

    if(H[r]==-1) H[r]=L[size]=R[size]=size;

    else {

        L[size]=L[H[r]]; R[L[H[r]]]=size;

        R[size]=H[r]; L[H[r]]=size;

    }

    size++;

}

void remove(int c){

    for (int i=D[c]; i!=c; i=D[i])

        L[R[i]]=L[i], R[L[i]]=R[i];

}

void resume(int c){

    for (int i=U[c]; i!=c; i=U[i])

        L[R[i]]=R[L[i]]=i;

}

int h(){///用精确覆盖去估算剪枝

    int ret=0;

    bool vis[maxc];

    memset (vis, false, sizeof(vis));

    for (int i=R[0]; i; i=R[i])

    {

        if(vis[i])continue;

        ret++;

        vis[i]=true;

        for (int j=D[i]; j!=i; j=D[j])

            for (int k=R[j]; k!=j; k=R[k])

                vis[C[k]]=true;

    }

    return ret;

}

int ans;

void Dance(int k){                //根据具体问题选择限制搜索深度或直接求解。  A*算法，此处只求最优解

    if(k+h()>=ans) return;

    if(!R[0]){

        if(k<ans)ans=k;

        return;

    }

    int c=R[0];

    for (int i=R[0]; i; i=R[i])

        if(S[i]<S[c])c=i;

    for (int i=D[c]; i!=c; i=D[i]){

        remove(i);

        for (int j=R[i]; j!=i; j=R[j])

            remove(j);

        Dance(k+1);

        for (int j=L[i]; j!=i; j=L[j])

            resume(j);

        resume(i);

    }

    return ;

}

void initL(int x){///col is 1~x,row start from 1

    for (int i=0; i<=x; ++i){

        S[i]=0;

        D[i]=U[i]=i;

        L[i+1]=i; R[i]=i+1;

    }///对列表头初始化

    R[x]=0;

    size=x+1;///真正的元素从m+1开始

    memset (H, -1, sizeof(H));

    ///mark每个位置的名字

}

DLX 重复覆盖 template

精确覆盖模板

struct DLX

{

  int n , sz;                                                 // 行数，节点总数

  int S[maxn];                                                // 各列节点总数

  int row[maxnode],col[maxnode];                              // 各节点行列编号

  int L[maxnode],R[maxnode],U[maxnode],D[maxnode];            // 十字链表

  int ansd,ans[maxn];                                         // 解

  void init(int n )

  {

    this->n = n ;

    for(int i = 0 ; i <= n; i++ )

    {

      U[i] = i ;

      D[i] = i ;

      L[i] = i - 1;

      R[i] = i + 1;

    }

    R[n] = 0 ;

    L[0] = n;

    sz = n + 1 ;

    memset(S,0,sizeof(S));

  }

  void addRow(int r,vector<int> c1)

  {

    int first = sz;

    for(int i = 0 ; i < c1.size(); i++ ){

      int c = c1[i];

      L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c];

      D[U[c]] = sz; U[c] = sz;

      row[sz] = r; col[sz] = c;

      S[c] ++ ; sz ++ ;

    }

    R[sz - 1] = first ; L[first] = sz - 1;

  }

  // 顺着链表A，遍历除s外的其他元素

  #define FOR(i,A,s) for(int i = A[s]; i != s ; 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) {++S[col[j]];U[D[j]] = j;D[U[j]] = j; }

    L[R[c]] = c;

    R[L[c]] = c;

  }

  bool dfs(int d){

    if(R[0] == 0 ){

      ansd = d;

      return true;

    }

    // 找S最小的列c

    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 true;

      FOR(j,L,i) restore(col[j]);

    }

    restore(c);

    return false;

  }

  bool solve(vector<int> & v){

    v.clear();

    if(!dfs(0)) return false;

    for(int i = 0 ; i< ansd ;i ++ ) v.push_back(ans[i]);

    return true;

  }

};

DLX solver;

int main()

{

  int n,m;

  while(scanf("%d%d",&n,&m)!=EOF)

  {

    solver.init(m);

    int c , x;

    vector<int> c1;

    for(int i = 1; i<= n ; i ++ )

    {

      scanf("%d",&c);

      c1.clear();

      for(int j = 0 ; j < c ; j ++ ){scanf("%d",&x);c1.push_back(x);}

      solver.addRow(i,c1);

    }

    vector<int> ans;

    bool flag ;

    flag = solver.solve(ans);

    if(flag )

    {

      int size1 = ans.size();

      printf("%d",size1);

      for(int i = 0 ; i < size1;i ++ )

        printf(" %d",ans[i]);

      printf("\n");

    }

    else printf("NO\n");

  }

  return 0;

}

巴特西

SPOJ 1771&&DLX精确覆盖，重复覆盖

最新文章

热门文章