题意:给定 n 个计算机的一个关系图,你可以停止每台计算机的一项服务,并且和该计算机相邻的计算机也会终止,问你最多能终止多少服务。
析:这个题意思就是说把 n 台计算机尽可能多的分成一些组,使得每组的的 u 是全集。我们可以用状压 DP 来解决,先处理输入,然后再处理每个子集,
dp[s] 表示状态为 s 时,最多能终止多少服务,dp[s] = max{dp[s^s0] +1 }。
代码如下:
- #pragma comment(linker, "/STACK:1024000000,1024000000")#include < cstdio > #include < string > #include < cstdlib > #include < cmath > #include < iostream > #include < cstring > #include < set > #include < queue > #include < algorithm > #include < vector > #include < map > #include < cctype > #include < cmath > #include < stack > #include < unordered_map > #include < unordered_set > #define debug() puts("++++");#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout) using namespace std;
- typedef long long LL;
- typedef pair < int,
- int > P;
- const int INF = 0x3f3f3f3f;
- const double inf = 0x3f3f3f3f3f3f;
- const double PI = acos( - 1.0);
- const double eps = 1e-8;
- const int maxn = (1 << 16) + 5;
- const int mod = 1e9 + 7;
- const int dr[] = { - 1,
- 1,
- 0,
- 0
- };
- const int dc[] = {
- 0,
- 0,
- 1,
- -1
- };
- const char * de[] = {
- "0000",
- "0001",
- "0010",
- "0011",
- "0100",
- "0101",
- "0110",
- "0111",
- "1000",
- "1001",
- "1010",
- "1011",
- "1100",
- "1101",
- "1110",
- "1111"
- };
- int n,
- m;
- const int mon[] = {
- 0,
- 31,
- 28,
- 31,
- 30,
- 31,
- 30,
- 31,
- 31,
- 30,
- 31,
- 30,
- 31
- };
- const int monn[] = {
- 0,
- 31,
- 29,
- 31,
- 30,
- 31,
- 30,
- 31,
- 31,
- 30,
- 31,
- 30,
- 31
- };
- inline bool is_in(int r, int c) {
- return r >= 0 && r < n && c >= 0 && c < m;
- }
- int dp[maxn];
- int a[20],
- s[maxn];
- int main() {
- int kase = 0;
- while (scanf("%d", &n) == 1 && n) {
- for (int i = 0; i < n; ++i) {
- scanf("%d", &m);
- a[i] = 1 << i;
- int x;
- while (m--) {
- scanf("%d", &x);
- a[i] |= 1 << x;
- }
- }
- for (int i = 0; i < (1 << n); ++i) {
- s[i] = 0;
- for (int j = 0; j < n; ++j) if (i & (1 << j)) s[i] |= a[j];
- }
- int all = (1 << n) - 1;
- dp[0] = 0;
- for (int i = 1; i < (1 << n); ++i) {
- dp[i] = 0;
- for (int j = i; j; j = (j - 1) & i) if (s[j] == all) dp[i] = max(dp[i], dp[i ^ j] + 1);
- }
- printf("Case %d: %d\n", ++kase, dp[all]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1976784.html