whosyourdaddy
题目：http://acm.hdu.edu.cn/showproblem.php?pid=3498
题意：英雄可以放一个技能，使得一个点和与其相邻的点受到伤害，问最少攻击几个点能够让所有的点都受到至少一次伤害。
题解：建模套DLX模板。
代码：
#include<cstdio>
#include<cstring>
#include<climits>
#define N 60
#define M 3600
using namespace std;
struct
{
int col,row;
} node[M];
int l[M],r[M],d[M],u[M],h[M],res[N],cntcol[N];
int dcnt=-1,minn;
int n,m;
bool visit[N],mark[N][N];
int H()
{
int count=0;
bool hash[N];
memset(hash,false,sizeof(hash));
for(int i=r[0]; i!=0; i=r[i])
{
if(hash[i]) continue;
//hash[i]=true;
count++;
for(int j=d[i]; j!=i; j=d[j])
for(int k=r[j]; k!=j; k=r[k])
hash[node[k].col]=true;
}
return count;
}
void addnode(int &x)
{
++x;
r[x]=l[x]=u[x]=d[x]=x;
}
void insert_row(int rowx,int x)
{
r[l[rowx]]=x;
l[x]=l[rowx];
r[x]=rowx;
l[rowx]=x;
}
void insert_col(int colx,int x)
{
d[u[colx]]=x;
u[x]=u[colx];
d[x]=colx;
u[colx]=x;
}
void dlx_init(int cols)
{
memset(h,-1,sizeof(h));
memset(cntcol,0,sizeof(cntcol));
dcnt=-1;
addnode(dcnt);
for(int i=1; i<=cols; ++i)
{
addnode(dcnt);
insert_row(0,dcnt);
}
}
void insert_node(int x,int y)
{
//printf("insert %d %d\n",x,y);
cntcol[y]++;
addnode(dcnt);
node[dcnt].row=x;
node[dcnt].col=y;
insert_col(y,dcnt);
if(h[x]==-1) h[x]=dcnt;
else insert_row(h[x],dcnt);
}
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]]=i;
r[l[i]]=i;
}
}
void DLX(int deep)
{
if(deep+H()>=minn) return;
if(r[0]==0)
{
if(minn>deep) minn=deep;
return;
}
int min=INT_MAX,tempc;
for(int i=r[0]; i!=0; i=r[i])
if(cntcol[i]<min)
{
min=cntcol[i];
tempc=i;
}
for(int i=d[tempc]; i!=tempc; i=d[i])
{
if(visit[node[i].row]) continue;
res[deep]=node[i].row;
remove(i);
for(int j=r[i]; j!=i; j=r[j]) remove(j);
DLX(deep+1);
for(int j=l[i]; j!=i; j=l[j]) resume(j);
resume(i);
}
return;
}
int main()
{
int k;
int a,b;
for(; ~scanf("%d%d",&n,&m);)
{
memset(mark,false,sizeof(mark));
dlx_init(n);//初始化
for(; m--;)
{
scanf("%d%d",&a,&b);
mark[a][b]=mark[b][a]=true;
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(mark[i][j]||i==j)
insert_node(i,j);
minn=INT_MAX;
DLX(0);
printf("%d\n",minn);
}
return 0;
}