[AtCoder] ABC 190 C – Bowls and Dishes

2021年2月17日

問題

方針

人 \( i \) は皿 \( C_i \) または \( D_i \) にボールを置くので、\( 2^K \) 通りのパターンが考えられます。したがって、ビット全探索を行います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M, K;
int A[100], B[100], C[16], D[16];
int best = 0;
int bit[16] = {};

void dfs(int n) {
    if (n == K) {
        int tmp = 0;
        int flag[100] = {};
        for (int i = 0; i < K; i++) {
            if (bit[i]) flag[C[i]] = 1;
            else flag[D[i]] = 1;
        }
        for (int i = 0; i < M; i++) {
            if (flag[A[i]] && flag[B[i]]) tmp++;
        }
        best = max(best, tmp);
        return;
    }
    dfs(n + 1);
    bit[n] = 1;
    dfs(n + 1);
    bit[n] = 0;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> C[i] >> D[i];
        C[i]--;
        D[i]--;
    }
    dfs(0);
    cout << best << "\n";
    return 0;
}