본문 바로가기

네트워크 플로우

L-R flow http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다. -간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인 1. MCMF로 모델링 a->b로의 간선이 하한이 l 상한이 r일 때 a->b로 (l , -1) , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다. 이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다. 이 때의 maxflow는 flow를 확인하여 구할 수 있다. 2. 디닉을 사용하는 방법 새로운 소스와 새로운 싱크를 만든다. 기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다. a->b로의 간선이 하.. 더보기
UVaOJ)11765 Component Placement 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865 N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다. 각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다. 이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다. 이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다. 이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면 하나의.. 더보기
BOJ)12922 블럭 퍼즐 문제: icpc.me/12922 1x1x2 블럭이 정사각형 그리드에서 이동할 때 게임승리를 불가능하게 뚫어야하는 구멍의 수를 출력하는 문제이다. 문제에서 블럭의 이동경로를 살펴보면 시작점에서 부터 4방향으로 3칸 떨어진 지점에만 서있을 수 있다. 이를 이용하여 모든 정점에서 3칸 떨어진 지점으로 그래프를 구성해주는데 이 때 간선의 capacity는 지나가는 경로에 뚫어야하는 구멍 수가 되야되고 해당 정점에 구멍을 뚫는 경우는 정점을 분할하여 사이에 capacity를 1로 주는걸로 그래프를 모델링 해주면 src에서 sink로의 mincut을 구해주면 답을 구해낼 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 더보기
BOJ)10319 좀비 아포칼립스 문제: icpc.me/10319 감염이 되기전에 병원으로 이동가능한 최대한의 사람을 구하는 문제이다. 문제에서 요구하는 조건이 곧 시작지점부터 병원까지의 최대유량을 구하는 문제인데 문제는 간선에 capacity말고도 단위시간이라는 제약 조건이 붙는다. 이걸 해결해주기 위해 단위시간만큼 정점을 분할 시켜주어 각 시간별로 주어진 정점들로 이루어진 그래프로 새로 재구성 시켜준 뒤 maximum flow를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868.. 더보기
BOJ)5651 완전 중요한 간선 문제: icpc.me/5651 어떤 그래프에서 플로우를 흘렸을 때 어떤 간선의 용량이 1 줄어들면 최대유량도 1 줄어들게 되는 간선을 완전 중요한 간선이라 할 때 그러한 간선의 수를 구하는 문제이다. 유량을 최대로 흘렸을 때 해당 간선에 용량을 줄였을 때 maximum flow에 직접적인 타격을 주려면 해당 유량이 해당 간선으로 밖에 통하지 못하여야 한다. 즉 유량 그래프에서 u->v로의 경로가 유일해야 한다. 답을 구하기 위해 유량을 흘려준 뒤 플로이드 워셜을 이용해 transitive closure를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565.. 더보기
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.. 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)9577 토렌트 문제: icpc.me/9577 시간마다 시드를 하나씩 받을 수 있고 각 시간에 시드를 받을 수 있는 사람과 각 사람이 받을 수 있는 시드의 종류가 주어졌을 때 시드를 전부 다운 받는 최소 시간을 출력하는 문제이다. 우리는 시간에 대한 정점과 시드에 대한 정점으로 나누어 이분 그래프를 형성해 준 다음 이분 매칭을 시도하는데 시간 정점중 t번째 정점까지 매칭 했을 때 최대매칭이 시드의 수와 일치할 경우 t초가 최단시간이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include using namespace std;in.. 더보기
BOJ)9169 나는 9999번 문제를 풀 수 있다 문제:icpc.me/9169 풀 수있다고 생각한 사람과 풀 수 없다고 생각한 사람의 생각이 주어지고 사람들의 친구 관계가 주어지는데 이 때 생각을 바꾸거나 친구사이에 투표한 결과가 서로 다른 관계의 수의 합의 최솟값을 구하는 문제이다. 우리는 풀 수 있다고 생각한 사람을 소스에 연결하고 풀 수 없다고 생각한 사람을 싱크에 연결 한 뒤 서로 다른 경우에 간선을 한 방향으로 같은 경우에 양방향으로 연결해줌으로서 그래프를 모델링 해준 뒤 cut의 개수를 구하면 어긋나는(생각이 다른) 경우의 개수이므로 min cut을 구해주면 된다. mincut은 Maxflow-Mincut Theorem에 의하여 maximum flow를 구해줌으로서 해결 된다. 123456789101112131415161718192021222.. 더보기