2017/06/12 썸네일형 리스트형 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? 꿀문제로만 채워넣어서 영양가는 좀 떨어지지만 기쁘다 더보기 이전 1 다음
