BOJ 1587 - 이분매칭

https://www.acmicpc.net/problem/1587

생각해보면 A집합 정점 갯수와 B집합 정점 갯수 둘 중 하나라도 짝수인 것이 있으면 같은 집합내에서 인접한애들끼리만 짝지어도 무조건 최대를 만들 수 있다는 것을 알 수 있다. 만약 둘 다 홀수라면 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 것 말고는 이득을 볼 것이 없다는 것을 알 수 있다. 따라서 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 간선이 있는지만 체크해서 답을 구하면 된다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기