LCR的愿望

时间限制：1s　内存限制：256M

题目描述

现在有$N$个神奇的盒子，编号为$1,2,…，N$
小A的朋友LCR有$M$个愿望，第$i$个愿望是在第$A_{i}$号和第$B_{i}$号盒子中都能有宝石。
现在小A有$K$个宝石，但是这些宝石非常神奇，第$i$个宝石只能放在第$C_{i}$号或者第$D_{i}$号盒子中。
小A现在想尽可能多的满足LCR的愿望，你能告诉小A他最多能够满足LCR多少个愿望吗？

输入格式

第一行两个用空格隔开的整数$N$，$M$。
接下来$M$行，每行两个数$A_i$, $B_i$，表示LCR的愿望。
紧接着一行一个整数$K$，表示宝石的数量。
最后$K$行，每行两个数，$C_i$, $D_i$，表示每个宝石能够放置的位置。

输出格式

输出一个整数，表示答案。
所有输入均为正整数。
$2≤N≤100$
$1≤M≤100$
$1≤A_{i}<B_{i}≤N$
$1≤K≤16$
$1≤C_{i}<D_{i}≤N$

做题思路

这个题数据不大，才$16$，用dfs即可
dfs框架如下：

void dfs(int step) {
    if (/*判断结束条件*/) {
        for (int i = 1; i <= m; i++) {
            // 计数
        }
        // 比较大小并统计
        return;
    }
    // 放入c[i]号盒子里
    dfs(step + 1);
    // 回溯，放入d[i]号盒子里
    dfs(step + 1);
    // 回溯
}

要注意的是一个盒子可以放多个宝石，统计时用++或者–会好些
main函数就不多说了

AC 代码

#include <iostream>
using namespace std;
int n, m, k, ans = 0;
int box[105];
int a[105], b[105], c[105], d[105];
void dfs(int step) {
    if (step > k) {
        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            if (box[a[i]] && box[b[i]])
                cnt++;
        }
        ans = max(ans, cnt);
        return;
    }

    box[c[step]]++;     // 放在c[i]号盒子里
    dfs(step + 1);
    box[c[step]]--;

    box[d[step]]++;     // 放在d[i]号盒子里
    dfs(step + 1);
    box[d[step]]--;
} 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d%d", &c[i], &d[i]);
    }
    dfs(1);
    printf("%d", ans);
    return 0;
}