HDU 3498 who's your daddy(DLX repeat cover)

Description

N个数字，M组”相邻”关系

消灭数字，攻击某个数字的时候，它本身以及与它相邻的数字会被消灭，求最少攻击次数

Sample Input

建模

问题转换

至少选出多少行,使每列都含有1

Dancing Links X 重复覆盖

①含1最少列，1所在行“们”必然不会被同时选中

②含1最少列中任选一行，将该行1元素所在列删除(这个过程会删掉列标元素——这样R[0] == 0可判作准出口，此列这个1却保留了——为了向右继续删)

③删除列是因为这列已经有1了，我以后选行的时候无需参考

④与精确覆盖思路上不同的是：精确覆盖删到只剩Head这个元素算成功，而重复覆盖只是把所有列标元素删掉算找到一个答案(当然它会遍历所有情况，找到最优的)

⑤与精确覆盖实现上不同的是：重复覆盖abandon与resume函数里的参数是id，而精确覆盖形参是列表元素，里面删除内容也不同

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 10010;


int n, m, res;
int cnt[105];///第i列1元素的个数
int L[MAX_V], R[MAX_V], U[MAX_V], D[MAX_V];
int Head[105];///第i行第一个1元素的ID,意义同列标元素
int Row[MAX_V], Col[MAX_V];///记录id所在行列
int ans[105];
bool vis[105];
vector<int> vec[105];

void init()
{
    for(int i = 0; i <= n; ++i)///初始化Head及m个列标元素
    {
        cnt[i] = 0;
        L[i] = i - 1;
        R[i] = i + 1;
        U[i] = i;
        D[i] = i;
        vec[i].clear();
        vec[i].push_back(i);
    }

    L[0] = n;
    R[n] = 0;

    memset(Head, -1, sizeof(Head));
}

void link(int row, int col, int id)
{
    Row[id] = row;
    Col[id] = col;

    U[id] = U[col];///我向上
    D[id] = col;///我向下
    D[ U[col] ] = id;///我上 下我
    U[col] = id;///我下 上我

    if(Head[row] == -1)
        Head[row] = L[id] = R[id] = id;
    else
    {
        L[id] = L[ Head[row] ];///我向左
        R[id] = Head[row];///我向右
        R[ L[ Head[row] ] ] = id;///我左 右我
        L[ Head[row] ] = id;///我右 左我
    }

    cnt[col]++;
}

///具体删除列，没有删除行(这一列有1了，我以后无需参考此列选行)
void abandon(int id)
{
    for(int i = D[id]; i != id; i = D[i])///空了id,便于后续删除列
        L[ R[i] ] = L[i], R[ L[i] ] = R[i];
}

void resume(int id)
{
    for (int i = D[id]; i != id; i = D[i])///空了id(因为上面就没abandon)
        L[ R[i] ] = R[ L[i] ] = i;
}

int h()
{
    int num = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = R[0]; i != 0; i = R[i])
    {
        if(vis[i])
            continue;
        num++;
        for(int j = D[i]; j != i; j = D[j])
            for(int k = R[j]; k != j; k = R[k])
                vis[ Col[k] ] = 1;
    }
    return num;///当前矩阵可拆解次数
}


void Dance(int deep)
{
    if(deep + h() >= res)///估价剪枝
        return ;

    if(R[0] == 0)///准出口(每次abandon都会ban掉列标元素)
    {
        if(deep < res)
            res = deep;
        return;
    }

    ///找到1的数目最少的一列  将列标元素存在c里
    int c = R[0];
    for(int i = R[0]; i != 0; i = R[i])
        if(cnt[i] < cnt[c])
            c = i;

    ///abandon(c);重复覆盖，某列含多个1也可选多行

    ///对于c列1元素所在行，遍历每行，看看选择哪一行合适
    ///最少含1列，1所在行必然不被同时选
    for(int i = D[c]; i != c; i = D[i])
    {
        ans[deep] = Row[i];///选当前行

        abandon(i);///我选这个1,后续无需参考此列(删除)
        for(int j = R[i]; j != i; j = R[j])
            abandon(j);///删除1元素所在行上 1元素所在列

        Dance(deep + 1);

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

    ///resume(c);

    ///return 0;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init();
        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        int id = n;///介于id的缘故,需要存完了再link
        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < vec[i].size(); ++j)
                link(i, vec[i][j], ++id);
        res = n;
        Dance(0);
        cout << res << '\n';
    }
    return 0;
}