首页 > 代码库 > UVA 10160 Servicing Stations（状态压缩+迭代加深）
UVA 10160 Servicing Stations（状态压缩+迭代加深）
【题目链接】 LInk
【题目大意】
给出一些点和边，选择一个点就能把这个点和相邻的点都覆盖，求最小点覆盖
【题解】
我们压缩点被覆盖的状态，迭代加深搜索覆盖的最小点数，
当剩余的点全部选上时都无法完全覆盖就剪枝。
【代码】
#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;const int N=36;int i,n,m,x,y,limit;LL st[N],Lft[N],Final;bool dfs(int pos,int d,LL St){ //printf("%d %d %lld\n",d,pos,st); if(St==Final)return 1; if(pos>n||d==limit)return 0; for(int i=pos;i<=n;i++){ if((St|Lft[i])!=Final)break; if(st[i]&St==st[i])continue; if(dfs(i+1,d+1,St|st[i]))return 1; }return 0;}void solve(){ Final=(1LL<<n)-1; for(int i=1;i<=n;i++)st[i]=1LL<<(i-1); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); st[x]|=1LL<<(y-1); st[y]|=1LL<<(x-1); }for(Lft[n]=st[n],i=n-1;i;i--)Lft[i]=(st[i]|Lft[i+1]); for(limit=1;limit<=n;limit++)if(dfs(1,0,0)){printf("%d\n",limit);break;}}int main(){ while(scanf("%d%d",&n,&m),n+m)solve(); return 0;}
UVA 10160 Servicing Stations（状态压缩+迭代加深）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。