首页 > 代码库 > UVa 11825 黑客的攻击（状态压缩dp）
UVa 11825 黑客的攻击（状态压缩dp）
https://vjudge.net/problem/UVA-11825
题意：
假设你是一个黑客，侵入了一个有着n台计算机（编号为0,1,...,n-1）的网络。一共有n种服务，每台计算机都运行着所有服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务。你的目标是让尽量多的服务完全瘫痪。
思路：
数学模型：把n个集合P1,P2,P3...Pn分成尽量多组，使得每组中所有集合的并集等于全集。
因为只要每一组是全集，我们就可以破坏一个服务，分组越多，破坏的服务当然也就越多。
首先，我们用二进制来记录每台计算机和和它相邻的计算机。
接下来用cover[]记录不同的分组情况。最后就是动态规划了，用f(s)表示子集S最多可以分成几组，状态转移方程如下：
if(cover[S0]==ALL) f[S]=max(f[S],f[S0^S]+1);
如果子集S0是全集，那么此时S0可以构成一个分组，那么S集合中出去S0的部分最大分组就是f[S0^S]。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 typedef long long LL;12 typedef pair<int,int> pll;13 const int INF=0x3f3f3f3f;14 const int maxn=1<<16+10;15 16 int n,m,x;17 int p[maxn],cover[maxn],f[maxn];18 19 int main()20 {21 //freopen("D:\\input.txt","r",stdin);22 int kase=0;23 while(~scanf("%d",&n) && n)24 {25 for(int i=0;i<n;i++)26 {27 p[i]=(1<<i);28 scanf("%d",&m);29 while(m--)30 {31 scanf("%d",&x);32 p[i]|=(1<<x);33 }34 }35 36 //枚举分组，并计算出每组的计算机集合，也就是cover[S]37 for(int S=0;S<(1<<n);S++)38 {39 cover[S]=0;40 for(int i=0;i<n;i++)41 {42 if(S&(1<<i)) cover[S]|=p[i];43 }44 }45 46 f[0]=0;47 int ALL=(1<<n)-1;48 for(int S=1;S<(1<<n);S++)49 {50 f[S]=0;51 for(int S0=S;S0;S0=(S0-1)&S)52 {53 if(cover[S0]==ALL) f[S]=max(f[S],f[S0^S]+1);54 }55 }56 printf("Case %d: %d\n",++kase,f[ALL]);57 }58 return 0;59 }
UVa 11825 黑客的攻击（状态压缩dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。