최소 컷 썸네일형 리스트형 UVaOJ)11765 Component Placement 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865 N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다. 각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다. 이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다. 이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다. 이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면 하나의.. 더보기 이전 1 다음