dfs로 그룹을 나누고 그룹에서 2명씩 짝지을 수 있는 최대 수를 구한 뒤 로봇춤 출 사람 있나 확인하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MV = 20; int n, m, cnt, res, g[MV + 1], ind[MV + 1], cn; vector<int> a[MV + 1], gr[MV + 1]; int gro(int x) { if (g[x]) return 0; ind[x] = cn++; g[x] = cnt; gr[cnt].push_back(x); for (int i : a[x]) { if (!g[i]) gro(i); } return 0; } int dp(int key, int gn, vector<int> &v) { if (v[key] != -1) return v[key]; int ans = 0; for (int i : gr[gn]) { if (key&(1 << ind[i])) continue; for (int j : a[i]) { if (key&(1 << ind[j])) continue; ans = max(ans, dp(key | (1 << ind[i]) | (1 << ind[j]), gn, v) + 2); } } v[key] = ans; return ans; } void gen(int gn) { vector<int> d; d.resize((1 << gr[gn].size()) + 1, -1); res += dp(0, gn, d); } int main() { scanf("%d%d", &n, &m); while (m--) { int u, v; scanf("%d%d", &u, &v); u--; v--; a[u].push_back(v); a[v].push_back(u); } for (int i = 0; i < n; i++) { if (g[i]) continue; cn = 0; cnt++; gro(i); } for (int i = 1; i <= cnt; i++) gen(i); if (res != n) res++; printf("%d", res); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 14941 호기심 (0) | 2018.02.17 |
|---|---|
| 14942 개미 (0) | 2018.02.17 |
| 15271 친구 팰린드롬 2 (0) | 2018.02.17 |
| 15312 이름 궁합 (0) | 2018.02.17 |
| 1371 가장 많은 글자 (0) | 2018.02.17 |