친하면서 이성인 친구와 춤을 출 수 있는 커플 수를 구하는게 요점이다.
남자, 여자로 나뉘고 친하다는 관계가 간선이므로 이분그래프가 성립한다.
이분매칭 돌리고 결과를 약간 손보면 된다.
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 | #include <stdio.h> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MV = 200; int n, m, ans, d[MV + 1]; bool c[MV + 1]; vector<int> a[MV + 1]; int dfs(int x) { if (x == -1) return 1; for (int i : a[x]) { if (c[i]) continue; c[i] = 1; if (dfs(d[i])) { d[i] = x; return 1; } } return 0; } int main() { memset(d, -1, sizeof(d)); scanf("%d%d", &n, &m); while (m--) { int u, v; scanf("%d%d", &u, &v); if (v % 2) swap(u, v); if ((u + v) % 2) a[u].push_back(v); } for (int i = 1; i <= n; i++) { memset(c, 0, sizeof(c)); ans += dfs(i); } ans *= 2; if (ans != n) ans++; printf("%d", ans); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 14942 개미 (0) | 2018.02.17 |
|---|---|
| 15270 친구 팰린드롬 (0) | 2018.02.17 |
| 15312 이름 궁합 (0) | 2018.02.17 |
| 1371 가장 많은 글자 (0) | 2018.02.17 |
| 14950 정복자 (0) | 2018.02.17 |