首页 > 代码库 > UVA 11825 Hackers' Crackdown
UVA 11825 Hackers' Crackdown
题解:
首先将相邻点进行二进制,保存在p[i]中
然后将不同组合的p[i]组合的值记录下来,保存在cover[i]中
然后从小到大进行dp
s0为集合s的子集
if(cover[ s0 ] == all - 1) f[s] = max( f[s], f[s ^ s0] + 1);
代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> const int INF = 1000000000; const int maxn = 1 << 16; int n, m, x; int p[ 16 ], cover[ maxn ]; int f[ maxn ]; int main() { int Case = 1; while( ~scanf( "%d", &n ) && n ) { memset( p, 0, sizeof( p ) ); for( int i = 0; i < n; i ++ ) { scanf( "%d", &m ); p[ i ] = ( 1 << i ); while( m -- ) { scanf( "%d", &x ); p[ i ] |= ( 1 << x ); } } int ALL = 1 << n; for( int s = 0; s < ALL; s ++ ) { cover[ s ] = 0; for( int i = 0; i < n; i ++ ) if( s & ( 1 << i ) ) cover[ s ] |= p[ i ]; } for( int s = 0; s < ALL; s ++ ) { f[ s ] = 0; for( int s0 = s; s0; s0 = ( s0 - 1 ) & s ) { if( cover[ s0 ] == ALL - 1 ) f[ s ] = max( f[ s ], f[ s ^ s0 ] + 1 ); } } printf( "Case %d: %d\n", Case ++, f[ ALL - 1 ] ); } return 0; }
UVA 11825 Hackers' Crackdown
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。