CuteWisp

[C++] AtCoder Beginner Contest 190 C번 Bowls and Dishes

04 Mar 2021 | PS

AtCoder Beginner Contest 190 C번 Bowls and Dishes

문제

https://atcoder.jp/contests/abc190/tasks/abc190_c abc190_c

풀이

접시가 N개가 있을때 m개의 조건이 있다 각 조건은 ai,bi번 접시에 공이 있다면 만족하는 조건이라고 할 때

k명의 사람이 각 ci 혹은 di번의 접시에 공을 놓는다고 할때 최대 몇개의 조건을 만족할까

k명의 사람이 ci 혹은 di를 선택하는 조건을 0 혹은 1로 생각하자

그러면 k명의 사람이 무언가를 선택하는것을 k-bits로 나타낼 수 있다.

K는 16보다 작기 떄문에 이를 모두 체크하여 최대값을 얻으면 정답

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc190/tasks/abc190_c
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n,m;
    cin >> n >> m;
    vll a(m), b(m);
    rep(i,m) cin >> a[i] >> b[i];
    ll k;
    cin >> k;
    vll c(k), d(k);
    rep(i,k) cin >> c[i] >> d[i];
    ll ans = 0;
    ll k2 = 1 << k;
    for (int i = 0 ; i < k2; i++) {
        vector<int> dish(n + 1);
        for (int s = 0; s < k; s++) {
            if (i >> s & 1) {
                dish[c[s]]++;
            } else {
                dish[d[s]]++;
            }
        }
        ll now = 0;
        for (int i = 0; i < m; i++) {
            if (dish[a[i]] == 0) continue;
            if (dish[b[i]] == 0) continue;
            now++;
        }
        ans = max(ans, now);
    }
 
    cout << ans;

    return 0;
}

Related posts