DLX 舞蹈链 精确覆盖 与 重复覆盖

时间：2023-03-09 07:47:41
DLX 舞蹈链 精确覆盖 与 重复覆盖

精确覆盖问题：给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1

还有重复覆盖问题

dancing links 是 一种数据结构，用来优化搜索，不算是一种算法。（双向循环十字链表）

参阅了白书训练指南上的模版，目前只有精确覆盖，等再补上重复覆盖

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 =  ; i <= n; i++ )

    {

      U[i] = i ;

      D[i] = i ;

      L[i] = i - ;

      R[i] = i + ;

    }

    R[n] =  ;

    L[] = n;

    sz = n +  ;

    memset(S,,sizeof(S));

  }

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

  {

    int first = sz;

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

      int c = c1[i];

      L[sz] = sz -  ; R[sz] = sz +  ; 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 - ] = first ; L[first] = sz - ;

  }

  // 顺着链表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[] ==  ){

      ansd = d;

      return true;

    }

    // 找S最小的列c

    int c = R[] ;

    FOR(i,R,) 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 + )) return true;

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

    }

    restore(c);

    return false;

  }

  bool solve(vector<int> & v){

    v.clear();

    if(!dfs()) return false;

    for(int i =  ; 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 = ; i<= n ; i ++ )

    {

      scanf("%d",&c);

      c1.clear();

      for(int j =  ; 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 =  ; i < size1;i ++ )

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

      printf("\n");

    }

    else printf("NO\n");

  }

  return ;

}

DLX 精确覆盖 template

//明天再写。。。

重复覆盖与精确覆盖做法稍有不同

精确覆盖：
首先选择当前要覆盖的列(含1最少的列)，将该列和能够覆盖到该列的行全部去掉，再枚举添加的方法。
枚举某一行r，假设它是解集中的一个，那么该行所能覆盖到的所有列都不必再搜，所以删除该行覆盖到的所有列，又由于去掉的列相当于有解，所以能够覆盖到这些列的行也不用再搜，删之。
重复覆盖：
首先选择当前要覆盖的列(同上)，将该列删除，枚举覆盖到该列的所有行：对于某一行r，假设它是解集中的一个，那么该行所能覆盖到的列都不必再搜，所以删除该行覆盖到的所有列。
注意此时不用删去覆盖到这些列的行，因为一列中允许有多个1。
这里有一个A*的优化：估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。

const int maxn=;

const int maxc=;

const int maxr=;

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]==-) 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=;

    bool vis[maxc];

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

    for (int i=R[]; 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){                //根据具体问题选择限制搜索深度或直接求解。

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

    if(!R[]){

        if(k<ans)ans=k;

        return;

    }

    int c=R[];

    for (int i=R[]; 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+);

        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=; i<=x; ++i){

        S[i]=;

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

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

    }///对列表头初始化

    R[x]=;

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

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

    ///mark每个位置的名字

}

DLX 重复覆盖 template

做了6个题：poj2074 poj3076 前者是9阶数独，后者是16阶数独，以16阶为例，把问题转化为矩阵，总共有16*16*4列，（行、列、小宫格、每个位置）。有16*16*16行。

hust1017 直接给出了精确覆盖问题的定义和模型。不用建模了，直接把输入建成矩阵即可。

zoj3209 矩阵覆盖，行数就是矩阵数，列数为要覆盖的大矩阵的格子数目（化为格子，输入的小矩阵也化为格子后一列就可以出来了）

上面都是精确覆盖，白书训练指南上的模版用的很舒心。

然后我想重复覆盖把这个模版改一改就好吧，结果

FZU 1686 这个题，用改出来的模版死活不过，一直超时，我觉着没啥问题了还是不过。直接去找了另外的模版。另外的题都用了

这题是告诉n*m的格子上有许多1（怪物），然后每次可以消灭（连续的）n1*m1格子内的怪物，问最少几次把所有怪物消灭掉，枚举所有的攻击方案，为行数，列数为1的个数

hdu2295 给定n个城市，m个地点可以建造雷达，最多建k个雷达，问雷达的最小覆盖半径为多少。二分枚举覆盖半径，用重复覆盖判定可否选k个以内的雷达覆盖完所有的城市。行数即为雷达个数，列为城市个数，1为每个雷达可以覆盖到的城市的。这个题目我用的上面的重复覆盖的模版，先把答案求出来然后在判定结果，结果一直超时+wa，之后改为直接在dance的时候限制搜索深度为k就AC了。错了好多次，中间hdu坏了2次，好无奈。。。。

相关文章