[COCI 2015/2016 #2] GEPPETTO

GitHub跳转原题关系图返回列表

把每份披萨看成一个原料子集，直接状压枚举所有 2^N 个子集并检查是否包含冲突对即可。

OJ: luogu

题目 ID: P7859

难度:普及-

标签:状态压缩枚举位运算图论

日期: 2026-06-21 05:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 N 种原料，给出 M 对冲突原料。

如果一份披萨同时包含某对冲突原料，这份披萨就不合法。 问一共有多少种合法的披萨。

思路

先看一个递归枚举的暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 405;

int n, m;
int x[MAXM], y[MAXM];
int choose_item[25];
int ans;

void dfs_choose(int u) {
    if (u == n + 1) {
        for (int i = 1; i <= m; i++) {
            if (choose_item[x[i]] && choose_item[y[i]]) {
                return;
            }
        }
        ans++;
        return;
    }

    choose_item[u] = 0;
    dfs_choose(u + 1);
    choose_item[u] = 1;
    dfs_choose(u + 1);
    choose_item[u] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：递归枚举每种原料选或不选，再检查是否出现冲突对。
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
    }

    ans = 0;
    memset(choose_item, 0, sizeof(choose_item));
    dfs_choose(1);
    cout << ans << '\n';
    return 0;
}

这个暴力对每种原料做“选 / 不选”的决策，最后检查是否合法。

本题虽然看起来是指数级枚举，但数据范围只有 N<=20。 这意味着总子集数最多只有：

2^20 = 1048576

完全可以直接做。

于是把每份披萨看成一个子集：

  • mask 的第 i 位为 1，表示第 i 种原料被选中

然后检查每条冲突边 (x,y)：

  • 如果 x,y 在这个子集中同时出现，那么这个子集不合法
  • 否则它就是一种可行披萨

所以这题其实就是在统计“冲突图的独立集个数”。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 405;

int n, m;
int x[MAXM], y[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    int ans = 0;
    int total = 1 << n;
    for (int mask = 0; mask < total; mask++) {
        bool ok = true;
        for (int i = 1; i <= m; i++) {
            if ((mask & (1 << x[i])) && (mask & (1 << y[i]))) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度 O(2NM)O(2^N M)，空间复杂度 O(M)O(M)。

总结

这题的关键不是设计复杂算法，而是敢于根据数据范围直接选择最朴素的状压枚举。