2017/06/20 썸네일형 리스트형 UVaOJ)10968 KuPellaKeS 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909 도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다. 연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다. 우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자. 그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나.. 더보기 이전 1 다음