BOJ 1587 - 이분 매칭

BOJ 1587 - 이분 매칭

$nA, nB$중, 짝수가 하나라도 있으면 그 쪽은 그쪽끼리 다 이어줄 수 있고 나머지는 최대한 이어주면 최적이다.

둘다 홀수일 땐, $+1$ 을 해줄 수 있는 홀수-홀수 번호를 잇는 간선이 하나라도 있으면 정답에 $+1$ 을 해주면 된다.

오늘 왜이리 그리디만 만나지

void solve() {  
   int n, m, M;  
   cin >> n >> m >> M;  
   if (n % 2 == 0 || m % 2 == 0) {  
      cout << n / 2 + m / 2;  
      return;   }  
   int ret = n / 2 + m / 2;  
   while (M--) {  
      int u, v;  
      cin >> u >> v;  
      u--, v--;  
      if (u % 2 == 0 && v % 2 == 0) {  
         cout << ret + 1;  
         return;      }  
   }  
   cout << ret;  
}