2017/06 썸네일형 리스트형 BOJ)1396 크루스칼의 공 문제: icpc.me/1396 lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다. x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다. 오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다. MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다. 즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다. 예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5)) 여기서 새로 생기.. 더보기 BOJ)10319 좀비 아포칼립스 문제: icpc.me/10319 감염이 되기전에 병원으로 이동가능한 최대한의 사람을 구하는 문제이다. 문제에서 요구하는 조건이 곧 시작지점부터 병원까지의 최대유량을 구하는 문제인데 문제는 간선에 capacity말고도 단위시간이라는 제약 조건이 붙는다. 이걸 해결해주기 위해 단위시간만큼 정점을 분할 시켜주어 각 시간별로 주어진 정점들로 이루어진 그래프로 새로 재구성 시켜준 뒤 maximum flow를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868.. 더보기 BOJ)5651 완전 중요한 간선 문제: icpc.me/5651 어떤 그래프에서 플로우를 흘렸을 때 어떤 간선의 용량이 1 줄어들면 최대유량도 1 줄어들게 되는 간선을 완전 중요한 간선이라 할 때 그러한 간선의 수를 구하는 문제이다. 유량을 최대로 흘렸을 때 해당 간선에 용량을 줄였을 때 maximum flow에 직접적인 타격을 주려면 해당 유량이 해당 간선으로 밖에 통하지 못하여야 한다. 즉 유량 그래프에서 u->v로의 경로가 유일해야 한다. 답을 구하기 위해 유량을 흘려준 뒤 플로이드 워셜을 이용해 transitive closure를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565.. 더보기 BOJ)1626 두 번째로 작은 스패닝 트리 문제: icpc.me/1626 두 번째로 작은 스패닝 트리를 구하는 문제이다. 우선 정점이 V개 간선이 E개인 그래프에서 MST를 구해준다. 그리고 MST를 구성할 때 사용하지 않은 E-V+1개의 간선에 대해서 해당 간선을 포함하는 MST를 구하여 답을 구해낸다.. 하지만 E-V+1번 크루스칼을 돌린다면 TLE를 보게 될것이다. 그렇다면 E-V+1개의 간선을 각각 포함하는 MST를 어떻게 구해낼 수 있을까? 우선 현재 보고 있는 간선이 1번 정점과 5번 정점을 연결한다고 가정해보자. 그렇다면 우리는 기존의 MST에서 1번 정점과 5번 정점을 연결해주어 N개의 간선을 가진 그래프를 생각해보자. 해당 그래프를 트리로 만드려면 하나의 간선을 제거해야한다. 이 때 제거되야 되는 간선은 1번 정점과 5번 정점을 .. 더보기 1500? 꿀문제로만 채워넣어서 영양가는 좀 떨어지지만 기쁘다 더보기 BOJ)10881 프로도의 선물 포장 문제: icpc.me/10881 세개의 상자를 하나의 큰 포장상자안에 넣어야 할 때 준비해야하는 포장상자의 최소 넓이를 구하는 문제이다. 우선 상자가 세개밖에 주어지지 않기 때문에 완전탐색을 생각해볼 수 있다. 세개의 상자를 배치하는 모양은 회전에 따라서 달라지지 않는 경우는 1열로 3상자를 배치하는 케이스와 2상자 위에 1 상자를 쌓아놓는 모양 두가지 밖에 없다. 때문에 주어진 조건으로 위의 경우에 해당 하는 모든 경우를 탐색하면 하나의 쿼리를 2*6^3의 시간만에 처리할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;pair a[6];int three(i.. 더보기 BOJ)11689 GCD(n,k) = 1 문제:icpc.me/11689 1~n까지의 수중에서 n과 서로소인 수를 구하는 문제이다. 소인수분해를 sqrt(n) 시간에 해결해준 뒤 포함-배제의 원리를 이용하여 서로소의 개수를 세주면된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include using namespace std;typedef long long ll;ll n;struct ele{ ll num, pos, state; ele(ll num, ll pos, ll state) :num(num), pos(pos), state(state) {}};vector .. 더보기 BOJ)2503 숫자 야구 문제:icpc.me/2503 각 자리의 숫자를 임의로 설정해 준 뒤 매 쿼리를 비교해주는 계산을 하더라도 O(1000*N)의 시간밖에 걸리지 않기 때문에 완전 탐색을 해주어 통과되는 숫자의 수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using namespace std;int n, r;struct query { int num, strike, ball; query(int num, int strike, int ball) :num(num), strike(strike), ball(ball) {} query() {} int getfirst().. 더보기 BOJ)1799 비숍 문제: icpc.me/1799 한 지점에 비숍이 세워진다면 그 지점을 통과하는 두개의 대각선에 있는 모든 지점에는 비숍이 세워질 수 없다. 이를 이용하여 왼쪽 아래로 향하는 대각선과 오른쪽 아래로 향하는 대각선을 가르는 정점들에게 각각 대각선의 번호를 매겨준 뒤 두 대각선으로 이루어진 이분 그래프에서의 최대 매칭을 구하는 문제로 변형시켜서 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include #include #include #includ.. 더보기 BOJ)7154 Job Postings 문제: icpc.me/7154 학생들이 원하는 일들과 일들의 개수 등이 주어질 때 학생들의 전체 만족도의 합의 최댓값을 구하는 문제이다. 학생들이 일을 선택하는 것을 학생과 일을 1:1로 매칭한다고 생각한다면 MCMF 문제로 만족도를 구할 수 있다. 모델링은 소스-> 일 -> 학생 -> 싱크로 구성해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include #include #include #include .. 더보기 이전 1 2 3 4 5 다음
