본문 바로가기

분류 전체보기

BOJ)1671 상어의 저녁식사 문제: icpc.me/1671 소스->상어->상어->싱크로 그래프를 모델링 한 뒤 최대유량을 구하여 N값에서 빼주면 남은 상어의 값을 구할 수 있다. 이때 주의해야 할 케이스가 있는데 두 상어의 크기 속도 지는이 전부 같다면 상어가 서로를 먹으려 할수도 있다. 이런 케이스에만 두 상어의 우위를 따로 주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include #include #include #include #i.. 더보기
BOJ)1867 돌멩이 제거 문제: icpc.me/1867 한 행을 쭉 이동하거나 한 열을 쭉 이동하면서 돌멩이를 치울 때 최소의 이동횟수로 돌멩이를 다 치울 수 있는지 구하는 문제이다. 우리는 x행 y열에 놓인 돌멩이를 x와 y를 연결시켜주는 이분 그래프 형태로 만들어준 뒤 돌멩이를 줍는다는 것은 결국 x와 y를 연결시키는 간선을 포함하는 것이다. 즉 우리는 간선들을 전부 포함시키는 최소한의 정점을 구하면 된다. 즉 최소 버텍스 커버를 구하는 문제로 해석된다. 이분 그래프에서의 최소 버텍스 커버문제는 이분 매칭과 동치이므로 최대매칭을 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #.. 더보기
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.. 더보기
BOJ)10090 Counting Inversions 문제: icpc.me/10090 1~N의 숫자들로 구성 된 수열이 주어질 때 먼저 나온 수보다 늦게 나온 수가 더 작은 경우의 수를 구하는 문제이다. N이 100만이기 때문에 N^2 완전 탐색으로 해결하기에는 문제가 있다. 따라서 우리는 쿼리를 받는 순서대로 온라인으로 처리를 해줄 것이다. 우선 내가 현재 보는 수가 x라면 나보다 작은 수의 개수는 x-1개다 그러면 나보다 먼저 나온 수들 중 나보다 작은 수의 개수가 a개라면 x에 의하여 결정되는 경우의 수는 x-1-a가 된다. 따라서 우리는 세그먼트 트리를 이용하여 수열을 받을때마다 x보다 작은 수의 개수들을 구해주어 x-1-a를 답에 더해주고 x의 위치에 1을 업데이트 시켜주면 된다. 주의 할점은 답을 저장할 자료형을 long long으로 사용해야 한.. 더보기
BOJ)2262 토너먼트 만들기 문제:icpc.me/2262 선수들의 토너먼트를 만들 때 매 시합마다 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 문제다. (x,y)의 토너먼트 그룹과 (z,w)의 토너먼트 그룹이 붙게되었을 때 랭킹 차는 abs(min(x~y)-min(z,w))이므로 이 식을 이용하여 점화식을 짜주면 된다. dp[lo][hi]의 정의는 lo부터 hi까지의 토너먼트를 만들 때 랭킹차의 총합의 최솟값이다. 점화식은 dp[lo][hi]= (i = lo~hi-1) min(dp[lo][i]+dp[i+1][hi]+abs(min(lo~i)-min(i+1~hi))) 이다. 1234567891011121314151617181920212223242526272829303132#include #include #include #define.. 더보기
BOJ)14226 이모티콘 문제: icpc.me/14226 이모티콘에 대한 연산이 주어질 때 이모티콘 S개를 치기 위해 필요한 시간의 최솟값을 구하는 문제이다. 화면에 존재하는 이모티콘을 복사해서 붙여넣는 경우는 2의 시간이 이모티콘 하나를 삭제하는 경우는 1의 시간이 걸린다 생각하고 다익스트라를 돌렸는데 WA를 계속 받았다. 문제 조건을 잘 확인해보니 한번 복사한 이모티콘을 여러번 붙여넣을 수 있는 것같았다. 그래서 다익스트라에서 pq의 3번째 인자로 붙여넣었을 경우의 붙여넣은 수를 인자로 주어 붙여넣기 하였을 경우 다시 붙여넣을 수 있게 소스를 수정하여 맞았다. 12345678910111213141516171819202122232425262728293031#include #include #include #include usin.. 더보기
디닉 알고리즘(Dinic's Algorithm) 디닉 알고리즘은 Maximum flow를 구하는 알고리즘 중에서 이분 그래프같은 특수한 환경에서 사용되는 알고리즘을 제외하고는 현재 PS분야에서 가장 빠르게 동작하는 알고리즘 입니다. 대부분의 유량 문제가 에드몬드 카프를 이용하여 해결 가능하지만 최근 몇몇 문제들은 디닉을 사용하지 않으면 시간초과를 보게 되는 경우도 많기 때문에 마음 편하게 디닉을 쓰시는걸 추천드립니다. 디닉 알고리즘의 시간 복잡도는 O(V^2*E)입니다. 그러면 디닉 알고리즘은 어떤 원리로 동작할까요? 우선 BFS를 이용하여 잔여용량이 0 이상인 간선에 대하여 레벨 그래프(level graph)라는 것을 만들어줍니다 잔여용량(residual capacity)이란 플로우에서 해당 간선의 기존 용량(c)에서 소스에서 흘려보낸 용량(f)를 .. 더보기
이분 매칭(Bipartite Matching) 네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다. 이분 그래프는 다음과 같은 모양을 띄고 있습니다. 위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다. 이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다. 간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고 우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지.. 더보기
BOJ)5398 틀렸습니다 문제: icpc.me/5398 충돌되는 단어들에 대하여 가로단어와 세로단어로 이루어진 이분 그래프를 형성시켜준 뒤 mincut을 구해주어 모든단어-mincut을 구해주면 되는 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include using namespace std;int t, h, v, x, y;char a[2001][2001];int c[2001][2001];int check[1001];int backmatch[1001];vector vt;bool dfs(int her.. 더보기

티스토리툴바