본문 바로가기

디닉 알고리즘

BOJ)12961 체스판2 문제:icpc.me/12961 체스판에 조건을 만족시키면서 동시에 채울 수 있는 타일의 최대 개수를 출력하는 문제이다. 타일의 모서리가 항상 검은칸을 덮게 체스판에 채울 경우 인접한 두 칸은 한 칸은 홀수 행에 한 칸은 짝수 행에 위치함을 알 수 있다. 고로 우리는 하얀 칸중 홀수 -> 검은 칸 -> 하얀 칸중 짝수 로 플로우를 흘려주어 얻을 수 있는 최대 유량이 답이 됨을 알 수 있다. 단 이 때 검은 칸을 통하여 플로우는 1만 흘러야 하므로 검은 칸을 정점 분할 시켜주어 정점 사이의 capacity를 1로 주어 풀어야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기
BOJ)3654 L퍼즐 문제:icpc.me/3654 L퍼즐 모양으로 패턴을 완성시킨다고 가정하였을 경우 B 정점은 인접한 W정점중 하나는 홀수행의 정점에 하나는 짝수행의 정점에 매칭이 되어야 한다. 따라서 두개의 플로우 모델링을 하여 하나는 홀수행의 W들과 B의 최대 매칭 하나는 짝수행의 W들과 B의 최대 매칭을 구한 뒤 두 값과 B의 개수가 같은지와 모든 W의 수와 2*B가 같은지 두 경우를 검사해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394.. 더보기