최대 유량 썸네일형 리스트형 BOJ)10319 좀비 아포칼립스 문제: icpc.me/10319 감염이 되기전에 병원으로 이동가능한 최대한의 사람을 구하는 문제이다. 문제에서 요구하는 조건이 곧 시작지점부터 병원까지의 최대유량을 구하는 문제인데 문제는 간선에 capacity말고도 단위시간이라는 제약 조건이 붙는다. 이걸 해결해주기 위해 단위시간만큼 정점을 분할 시켜주어 각 시간별로 주어진 정점들로 이루어진 그래프로 새로 재구성 시켜준 뒤 maximum flow를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868.. 더보기 BOJ)12961 체스판2 문제:icpc.me/12961 체스판에 조건을 만족시키면서 동시에 채울 수 있는 타일의 최대 개수를 출력하는 문제이다. 타일의 모서리가 항상 검은칸을 덮게 체스판에 채울 경우 인접한 두 칸은 한 칸은 홀수 행에 한 칸은 짝수 행에 위치함을 알 수 있다. 고로 우리는 하얀 칸중 홀수 -> 검은 칸 -> 하얀 칸중 짝수 로 플로우를 흘려주어 얻을 수 있는 최대 유량이 답이 됨을 알 수 있다. 단 이 때 검은 칸을 통하여 플로우는 1만 흘러야 하므로 검은 칸을 정점 분할 시켜주어 정점 사이의 capacity를 1로 주어 풀어야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기 BOJ)4627 뛰어라 도마뱀 문제: icpc.me/4627 도마뱀이 맨해튼 거리가 D이하인 거리를 이동 할 수 있을 때 탈출을 하지 못하는 도마뱀의 수를 정하면 된다. 문제를 잘 읽어보면 같은 시간에는 최대 하나의 도마뱀만 기둥에 서 있을 수 있고 기둥에는 최대 도약 횟수가 정해져 있다. 이를 이용하여 그래프를 모델링을 하면 소스->도마뱀들의 처음 위치 각 방-> 맨하탄 거리가 D이내인 방 외각->Destination 으로 모델링을 할 수 있다. 이 때 우리는 최대 도약 횟수를 생각해야 하므로 정점들을 분할하여 정점을 분할하는 간선의 가중치를 최대 도약횟수로 주고 최대유량을 구해주면 원하는 답을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383.. 더보기 이전 1 다음