bipartite matching 2

BAEKJOON 1017 - 소수 쌍

문제: https://www.acmicpc.net/problem/1017 우선 에라토스테네스의 체 방법으로 2000 까지 소수를 구해놓고 앞의 1014번 문제에서 사용한적이 있던 network flow (Ford Fulkerson algorithm) 방법으로 bipartite matching 문제를 푸는 방법을 이용하여 푼 문제입니다.처음에 이분 매칭(bipartite matching) 의 조건을 구성하는 것이 생각하기 어려운 부분일 수 있는데 주어진 숫자를 짝수와 홀수로 나눠 이분 그래프를 만드는 것이 중요합니다. 짝수와 짝수 또는 홀수와 홀수로는 무조건 짝수값이 나오기 때문에 소수가 절대 될 수 없고 이 점 때문에 이분 그래프가 성립이 될 수 있는거죠.그리고 첫 번째 주어진 값과 연결될 수 있는 값을..

BAEKJOON 1014 - 컨닝

문제: https://www.acmicpc.net/problem/1014 알고리즘 책에서 봤던 network flow (Ford Fulkerson algorithm) 방법으로 bipartite matching 문제를 푸는 방법을 참고하여 풀어봤습니다.알고리즘 책에 예제로 있던 문제는 비숍을 놓는 문제로 놓여지는 비숍에 따른 두 개의 대각선으로 id를 정했다면 이 문제는 가로 줄의 홀수, 짝수 열로 id를 정해야되고 같은 홀수줄 또는 짝수줄은 절대 공통 원소를 가질 수 없으므로 이분 그래프가 됩니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..