$$\color{Purple}{kuangbin题解目录}$$
描述
题意
给定$N(2 \le N \le 55)$个点,$M(0 \le M \le N\times N)$条无向边,删除一个点会把与其相邻的点一起删掉。问最少删几次能够删掉全部点。
思路
重复覆盖问题
: 选定最少的行,使得每列至少有一个1。- $N$个点看成$N$个要被覆盖的列,每一个点作为
一行
,与其相邻的点的位置在这一行中标为 $1$,还有它自已的位置也标记为$1$.
精确覆盖
一列只能有一个$1$,所以在考虑某一列时,要在此列有$1$的所有行全部删掉,从这些行中选一行作为此次被选中的行,选中行中有$1$的列不能再考虑,而且在对应选中有$1$的列中有$1$的那些行也要全部删掉;
但重复覆盖
允许一列由多个$1$,所以考虑某一列时,也是选其中一行,但只删被选中的那一行,选中行中有$1$ 的列不需再考虑删列,在对应选中有$1$的列中有$1$的那些行全都不能删。精确覆盖删列
的方式是:在列头哨兵那里改下$left$和$right$的标记就算是删掉整列了;
重复覆盖的删列
的方式是:整列的所有元素都要处理$left$和$right$标记。
精确覆盖删行
的方式是:对这行的所有元素都要改$up$和$down$的标记;
重复覆盖的删行
的方式是:不改$up$和$down$标记,但对这行所有的元素都进行(重复覆盖式的)删列,因为这行所有$1$所在列都被删掉,所以没有列可以访问这一行,所以相当于已经删行。重复覆盖
删行删得少,要加个估价函数
来剪枝
。估价函数就是:用精确覆盖
来计算目前至少仍需添加多少行才能完成覆盖。- 与
精准覆盖
的差别在于删除、恢复和dance函数
估价函数
:将能够覆盖当前列的所有行全部选中,去掉这些行能够覆盖到的列,将这个操作作为一层深度。重复此操作直到所有列全部出解的深度是多少。如果当前深度加上这个估价函数返回值,其和已然不能更优(也就是已经超过当前最优解),则直接返回,不必再搜。
代码
// Problem: whosyourdaddy
// Contest: HDOJ
// URL: http://acm.hdu.edu.cn/showproblem.php?pid=3498
// Memory Limit: 65 MB
// Time Limit: 20000 ms
// Date: 2023-01-14 15:20:10
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 60
#define MAXM 3710
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m;
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXM];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int res;
int vis[MAXN];
int f()
{
int res=0;
memset(vis,0,sizeof(vis));
for(int i=node[0].Right;i!=0;i=node[i].Right)
if(vis[i]==0)
{
vis[i]=1;
res++;
for(int j=node[i].Down;j!=i;j=node[j].Down)
for(int k=node[j].Right;k!=j;k=node[k].Right)
vis[node[k].col]=1;
}
return res;
}
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
res=inf;
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(按顺序放)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
//与精准覆盖的差别在于删除、恢复和dance函数
void Remove_Link(int y)//删除该列
{
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
node[node[i].Right].Left=node[i].Left;
node[node[i].Left].Right=node[i].Right;
}
}
void Resume_Link(int y)//恢复该列
{
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
{
node[node[i].Right].Left=i;
node[node[i].Left].Right=i;
}
}
void dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(f()+depth>=res)//剪枝
return ;
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
res=depth;
return ;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
Remove_Link(i);//注不能是node[i].col
for(int j=node[i].Right;j!=i;j=node[j].Right)
Remove_Link(j);
dance(depth+1);
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)
Resume_Link(j);
Resume_Link(i);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(cin >> n >> m)
{
Init_Node(n);
for(int i=1;i<=m;i++)
{
int a,b;
cin >> a >> b;
Insert_Node(a,b);
Insert_Node(b,a);
}
for(int i=1;i<=n;i++)//自己可以覆盖自己
Insert_Node(i,i);
dance(0);
cout << res << endl;
}
return 0;
}
列删完了代表着需要的行数找到了,但是这时的行数不一定是最佳的答案,还要回溯
牛子,在你这里我学会了