Hdu3498-whosyourdaddy(精确覆盖模板题)

Problem Description

sevenzero liked Warcraft very much, but he haven‘t practiced it for several years after being addicted to algorithms. Now, though he is playing with computer, he nearly losed and only his hero Pit Lord left. sevenzero is angry, he decided to cheat to turn defeat into victory. So he entered "whosyourdaddy", that let Pit Lord kill any hostile unit he damages immediately. As all Warcrafters know, Pit Lord masters a skill called Cleaving Attack and he can damage neighbour units of the unit he attacks. Pit Lord can choice a position to attack to avoid killing partial neighbour units sevenzero don‘t want to kill. Because sevenzero wants to win as soon as possible, he needs to know the minimum attack times to eliminate all the enemys.

Input

There are several cases. For each case, first line contains two integer N (2 ≤ N ≤ 55) and M (0 ≤ M ≤ N*N),and N is the number of hostile units. Hostile units are numbered from 1 to N. For the subsequent M lines, each line contains two integers A and B, that means A and B are neighbor. Each unit has no more than 4 neighbor units. The input is terminated by EOF.

Output

One line shows the minimum attack times for each case.

Sample Input

5 4

1 2

1 3

2 4

4 5

6 4

1 2

1 3

1 4

4 5

Sample Output

2

3

解析:裸的精确覆盖问题,不过要加优化,不过也是模板。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int INF=1e9+7;
const int ms=60;
const int maxn=ms*ms;
int N,M,ans;
struct DLX
{
    int n,id;
    int L[maxn],R[maxn],U[maxn],D[maxn];
    int C[maxn],S[maxn],loc[maxn][2];
    void init(int nn=0) //传列长
    {
        n=nn;
        for(int i=0;i<=n;i++) U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;
        L[0]=n; R[n]=0;
        id=n;
        memset(S,0,sizeof(S));
    }
    void AddRow(int x,int col,int A[]) //传入参数是行标号,列长,列数组
    {
        bool has=false;
        int first=id+1;
        for(int y=1;y<=col;y++)
        {
            if(A[y]==0) continue;
            has=true;
            ++id;
            L[id]=id-1; R[id]=id+1;
            D[id]=y; U[id]=U[y];
            D[U[y]]=id; U[y]=id;
            loc[id][0]=x,loc[id][1]=y;
            C[id]=y; S[y]++;
        }
        if(!has) return;
        R[id]=first; L[first]=id;
    }
    void Remove(int Size)
    {
        for(int j=D[Size];j!=Size;j=D[j])//将左右两边连接
            L[R[j]]=L[j],R[L[j]]=R[j];
    }
    void Resume(int Size)
    {
        for(int j=U[Size];j!=Size;j=U[j])//恢复
            L[R[j]]=R[L[j]]=j;
    }
    bool vis[ms];//标记行是否访问过
    int h() //启发式函数
    {
        int ret=0;
        int i,j,k;
        memset(vis,0,sizeof(vis));
        for(i=R[0];i;i=R[i])
        {
           if(vis[i]) continue;
           ret++;
           for(j=D[i];j!=i;j=D[j]) //所有关联的标记了
               for(k=R[j];k!=j;k=R[k]) vis[C[k]]=1;
        }
        return ret;
    }
    void dfs(int step)
    {
        if(step+h()>=ans) return;
        if(R[0]==0){ ans=min(ans,step); return; }
        int Min=INF,c=-1;
        for(int i=R[0];i;i=R[i]) if(Min>S[i]){ Min=S[i]; 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);
            dfs(step+1);
            for(int j=L[i];j!=i;j=L[j]) Resume(j);
            Resume(i);
        }
        return;
    }
}dlx;
int Mart[ms][ms];
int main()
{
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        dlx.init(N);
        ans=55;
        memset(Mart,0,sizeof(Mart));
        for(int i=1;i<=N;i++) Mart[i][i]=1;
        while(M--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            Mart[x][y]=Mart[y][x]=1;
        }
        for(int i=1;i<=N;i++) dlx.AddRow(i,N,Mart[i]);
        dlx.dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

代码

时间: 08-06

Hdu3498-whosyourdaddy(精确覆盖模板题)的相关文章

hust 1017 dancing links 精确覆盖模板题

最基础的dancing links的精确覆盖题目 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 #define N 1005 8 #define MAXN 1000100 9 10 struct DLX{ 11 int n , m , size;//size表示当前dlx表中有多少

DLX精确覆盖与重复覆盖模板题

hihoCoder #1317 : 搜索四·跳舞链 原题地址:http://hihocoder.com/problemset/problem/1317 时间限制:10000ms 单点时限:1000ms 内存限制:256MB   描述 小Ho最近遇到一个难题,他需要破解一个棋局. 棋局分成了n行,m列,每行有若干个棋子.小Ho需要从中选择若干行使得每一列有且恰好只有一个棋子. 比如下面这样局面: 其中1表示放置有棋子的格子,0表示没有放置棋子. 对于上面这个问题,小Ho经过多次尝试以后得到了解为选

HUST 1017 - Exact cover (Dancing Links 模板题)

1017 - Exact cover 时间限制:15秒 内存限制:128兆 自定评测 5584 次提交 2975 次通过 题目描述 There is an N*M matrix with only 0s and 1s, (1 <= N,M <= 1000). An exact cover is a selection of rows such that every column has a 1 in exactly one of the selected rows. Try to find o

SPOJ 1771&amp;&amp;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的模板就知道,它其实在选中一列之后,是会枚举列上的行值,

POJ 3047 Sudoku DLX精确覆盖

DLX精确覆盖.....模版题 Sudoku Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8336   Accepted: 2945 Description In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example, . 2 7 3 8 . . 1 . . 1 . .

ZOJ 3209 Treasure Map(DLX精确覆盖)

Your boss once had got many copies of a treasure map. Unfortunately, all the copies are now broken to many rectangular pieces, and what make it worse, he has lost some of the pieces. Luckily, it is possible to figure out the position of each piece in

POJ 3076 Sudoku DLX精确覆盖

DLX精确覆盖模版题..... Sudoku Time Limit: 10000MS   Memory Limit: 65536K Total Submissions: 4416   Accepted: 2143 Description A Sudoku grid is a 16x16 grid of cells grouped in sixteen 4x4 squares, where some cells are filled with letters from A to P (the fi

POJ 3074 Sudoku DLX精确覆盖

DLX精确覆盖.....模版题 Sudoku Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8336   Accepted: 2945 Description In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example, . 2 7 3 8 . . 1 . . 1 . .

[DLX精确覆盖] hdu 1603 A Puzzling Problem

题意: 给你n块碎片,这些碎片不能旋转.翻折. 问你能不能用当中的某些块拼出4*4的正方形. 思路: 精确覆盖裸题了 建图就是看看每一个碎片在4*4中能放哪些位置,这个就作为行. 列就是4*4=16个位置再加上n个碎片也就是16+n 然后注意下成立的判定就好了 代码: #include"stdio.h" #include"algorithm" #include"string.h" #include"iostream" #inc