디닉 썸네일형 리스트형 BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기 BOJ)9169 나는 9999번 문제를 풀 수 있다 문제:icpc.me/9169 풀 수있다고 생각한 사람과 풀 수 없다고 생각한 사람의 생각이 주어지고 사람들의 친구 관계가 주어지는데 이 때 생각을 바꾸거나 친구사이에 투표한 결과가 서로 다른 관계의 수의 합의 최솟값을 구하는 문제이다. 우리는 풀 수 있다고 생각한 사람을 소스에 연결하고 풀 수 없다고 생각한 사람을 싱크에 연결 한 뒤 서로 다른 경우에 간선을 한 방향으로 같은 경우에 양방향으로 연결해줌으로서 그래프를 모델링 해준 뒤 cut의 개수를 구하면 어긋나는(생각이 다른) 경우의 개수이므로 min cut을 구해주면 된다. mincut은 Maxflow-Mincut Theorem에 의하여 maximum flow를 구해줌으로서 해결 된다. 123456789101112131415161718192021222.. 더보기 BOJ)1671 상어의 저녁식사 문제: icpc.me/1671 소스->상어->상어->싱크로 그래프를 모델링 한 뒤 최대유량을 구하여 N값에서 빼주면 남은 상어의 값을 구할 수 있다. 이때 주의해야 할 케이스가 있는데 두 상어의 크기 속도 지는이 전부 같다면 상어가 서로를 먹으려 할수도 있다. 이런 케이스에만 두 상어의 우위를 따로 주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include #include #include #include #i.. 더보기 BOJ)11377 열혈강호3 문제: icpc.me/11377 사람과 일을 1:1로 매칭할 때 최대매칭을 구하는데 일을 여러번 할 수 있는 직원의 수 K가 별도로 주어질 때의 최대매칭을 구하는 문제이다. 이분 매칭에서의 최대매칭을 구하는데 우리는 중간에 BRIDGE를 둬서 소스에서 BRIDGE로 K만큼 흘려준 뒤 BRIDGE에서 이분 그래프의 좌측 으로 1씩 capacity를 주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #incl.. 더보기 디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 더보기 BOJ)4627 뛰어라 도마뱀 문제: icpc.me/4627 도마뱀이 맨해튼 거리가 D이하인 거리를 이동 할 수 있을 때 탈출을 하지 못하는 도마뱀의 수를 정하면 된다. 문제를 잘 읽어보면 같은 시간에는 최대 하나의 도마뱀만 기둥에 서 있을 수 있고 기둥에는 최대 도약 횟수가 정해져 있다. 이를 이용하여 그래프를 모델링을 하면 소스->도마뱀들의 처음 위치 각 방-> 맨하탄 거리가 D이내인 방 외각->Destination 으로 모델링을 할 수 있다. 이 때 우리는 최대 도약 횟수를 생각해야 하므로 정점들을 분할하여 정점을 분할하는 간선의 가중치를 최대 도약횟수로 주고 최대유량을 구해주면 원하는 답을 얻을 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383.. 더보기 이전 1 다음
