네트워크 플로우 썸네일형 리스트형 BOJ)1017 소수 쌍 문제: icpc.me/1017 N개의 수가 주어질 때 주어진 모든 수를 짝을 지을 때 모든 각각의 짝의 합이 소수가 되도록 할 때 첫 번째 수와 매칭 될 수 있는 모든 수를 구하는 문제이다. 어떤 수 a와 b가 서로 다를 경우 a+b가 소수가 되기 위해서는 a와 b가 짝수와 홀수로 나누어져야한다. 즉 우리는 짝수와 홀수로 이분 그래프 형태로 그래프를 모델링 해준 후 이분 매칭을 구해주어 n/2만큼 매칭 될 경우 1번 정점과 매칭 된 정점을 역추적 해주어 답에 넣어준 후 그 간선만 제거하고 다시 이분매칭을 실행함을 반복해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535.. 더보기 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.. 더보기 BOJ)11376 열혈강호2 문제: icpc.me/11376 사람 N명과 할일 M명이 있을 때 각 사람이 최대 두개일을 할 수 있을 때의 최대매칭을 구하면 되는 문제이다. 우리는 각 사람에 대해서 이분 매칭을 2번씩 돌려주어 최대매칭을 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #define MAX_N 1000using namespace std;vector vt;int b[MAX_N + 1], visited[MAX_N + 1], n, m, x;bool dfs(int here) { if (visited[here])return false; visited[her.. 더보기 디닉 알고리즘(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 2 다음
