hust1017 Exact cover(dancing link)

时间：2010-04-04 来源：chhaya

http://acm.hust.edu.cn/thanks/problem.php?id=1017

给一个01矩阵，求哪些行能使每一列正好有一个1.

这是Donald E.Knuth介绍dancing link时用的一个例子。
论文中文翻译在http://sqybi.com/works/dlxcn/#p11
原文PDF下载在http://arxiv.org/abs/cs/0011047
我中英文对照着看的，翻译的跟原文意思差不多，算是很好了。
多看几遍理解了舞蹈步骤基本上就能做了，就是搞十字链表很麻烦，还要构造比较好的数据结构，一开始我搞复杂化了，要么超空间，要么指针指错误，调试了n遍，重写了一遍终于一个个问题都解决了。

虽然Accept了，可是花了5s+，汗。。。。优化空间还很大，只是不知道怎么搞了。

#include <stdio.h>
#include <string.h>
#define N 1000 //最多N行N列

#define inf 10000000
int posx[N][N], posy[N][N];

typedef struct Node
{
  int key;
  int cnt; //此列有几个1

  struct Node *root; //指向列头

  struct Node *up;
  struct Node *down;
  struct Node *left;
  struct Node *right;
}Node;

Node link[N*N]; //十字链表

int column, raw; //列数，行数

int flag, top, stack[N];

int build()
{
    int i, j;
    int cur, pre, first;

    //构造列头， link[0]是head，link[1]---link[column]是列头， link[column]之后的是有1的节点
    for(i=1; i<=column; i++)
    {
        link[i-1].right = &link[i];
        link[i].left = &link[i-1];
        link[i].cnt = 0;
        link[i].key = i;
    }
    link[0].left = &link[column];
    link[0].key = 0;
    link[column].right = &link[0];

    /*deal with column*/
    for(i=1; i<=column; i++)
    {
        cur = posy[i][1] * N + i;
        pre = cur;
        link[cur].up = &link[i];
        link[i].down = &link[cur];
        link[cur].root = &link[i];
        link[cur].key = cur;
        link[i].cnt++;
        for(j=2; j<=posy[i][0]; j++)
        {
            cur = posy[i][j] * N + i;
            link[pre].down = &link[cur];
            link[cur].key = cur;
            link[cur].up = &link[pre];
            link[cur].root = &link[i];
            link[i].cnt++;
            pre = cur;
        }
        link[pre].down = &link[i];
        link[i].up = &link[pre];

        if(link[i].cnt == 0)
            return 0;

    }

    /*deal with rows*/
    for(i=1; i<=raw; i++)
    {
        first = i*N+posx[i][1];
        pre = first;
        for(j=2; j<=posx[i][0]; j++)
        {
            cur = i*N+posx[i][j];
            link[pre].right = &link[cur];
            link[cur].left = &link[pre];
            pre = cur;
        }
        link[pre].right = &link[first];
        link[first].left = &link[pre];
    }
//    print();
    return 1;
}

//移除列，同时把一行上的1都移除
void remove1(Node *c)
{
    Node *p, *q;
    c->left->right = c->right;
    c->right->left = c->left;

    for(p=c->down; p->key!=c->key; p=p->down)
    {
            p->root->cnt--;
        for(q=p->right; q->key!=p->key;q=q->right)
        {

            q->down->up = q->up;
            q->up->down = q->down;
        }
    }
}

//把移除的恢复
void resume(Node *c)
{
    Node *p, *q;
    c->right->left = c;
    c->left->right = c;
    for(p=c->up; p->key!=c->key; p=p->up)
    {
        p->root->cnt++;
        for(q=p->left; q->key!=p->key; q=q->left)
        {

            q->up->down = q;
            q->down->up=q;
        }
    }
}

int dfs(int k)
{
    int i;
    int s;
    Node *c, *p, *q;

    if(flag)
        return 1;
    if(link[0].right == &link[0])
    {
        printf("%d", top);
        for(i=0; i<top; i++)
            printf(" %d", stack[i]);
        printf("\n");
        flag = 1;
        return 1;
    }

    //找到1最少的列，这个不搞也行，只是为了优化
    s = inf;
    for(p=link[0].right; p->key != link[0].key; p=p->right)
    {
        if(p->cnt < s)
        {
            s = p->cnt;
            c = p;
        }
    }
    remove1(c);
    /*    printf("after remove %d: \n",c->key);//////////////////
        print();/////////////////////////////////////////
*/
    for(p=c->down; p->key!=c->key; p=p->down)
    {
        stack[top++] = p->key/N;
        for(q=p->right; q->key!=p->key; q=q->right)
        {
            remove1(q->root);
        }
        if(dfs(k+1))
            return 1;
        for(q=p->left; q->key!=p->key; q=q->left)
        {
            resume(q->root);
        }
        top--;
    }
    resume(c);
    return 0;
}

int main()
{
  int i, j, tmp;

  freopen("1017.in", "r", stdin);
  while(scanf("%d %d", &raw, &column) != EOF)
  {
     memset(posx, 0, sizeof(posx));
     memset(posy, 0, sizeof(posy));
     memset(stack, 0, sizeof(stack));
     memset(link, 0, sizeof(link));
    for(i=1; i<=raw; i++)
    {
      scanf("%d", &posx[i][0]);
      for(j=1; j<=posx[i][0]; j++)
      {
        scanf("%d", &tmp);
        posx[i][j] = tmp;
        posy[tmp][++posy[tmp][0]] = i;
      }
    }

    if(build() == 0)
    {
        printf("NO\n");
        continue;
    }

    flag = 0;
    top = 0;
    dfs(0);

    if(!flag)
        printf("NO\n");
  }
  return 0;

}