hopcroft-karp 썸네일형 리스트형 BOJ)13166 범죄 파티 문제: icpc.me/13166 범죄자 N명과 친구 2*N명의 친구 관계와 임계점이 주어질 때 모든 범죄자가 친구랑 매칭 될 수 있는 파티 비용의 최솟값을 구하는 문제이다. 파티 비용의 최솟값을 파라메트릭 서치로 탐색할건데 이 때 탐색 기준은 mid를 파티 비용으로 정했을 때 모든 범죄자가 친구들과 매칭 되야 하므로 범죄자와 친구의 이분 매칭이 N이 됨을 기준으로 한다. 단, 정점의 개수가 20만이나 되므로 일반 이분매칭 소스로는 TLE를 보게되니 호프크로프트 카프 알고리즘을 이용하여 구해줘야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 더보기 BOJ)3736 System Engineer 문제: icpc.me/3736 작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다. 정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #define INF 987654321using namespace std;struct hopcroft_karp { in.. 더보기 이전 1 다음