2017/06/19 썸네일형 리스트형 UVaOJ)12645 Water Supply 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기 UVaOJ)11751 Installing Diagnostic Software 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2851 확실한 번역은 모르겠지만 대략적인 설명은 간선이 주어질 때 해당 간선에 연결 된 두정점중 하나는 반드시 소프트웨어가 설치되어야 할 때 최소비용으로 소프트웨어를 설치하는 방법을 출력하는 문제이다. 소프트웨어 설치비용은 i번 정점의 경우 2^i의 비용이 소모된다. 즉 i번 정점에 소프트웨어를 설치하는건 0~i-1번 정점 모두에 소프트웨어를 설치하는것보다 비싸다 그렇기 때문에 최대한 작은 정점에 소프트웨어를 설치해야한다. 이를 위하여 간선에 연결 된 두 정점 중 작은 정점에 설치를 해야함은 자명하다. 그렇다면 이제 문제는 간.. 더보기 이전 1 다음