https://www.acmicpc.net/problem/14285 14285번: 간선 끊어가기 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net 설명은 복잡하지만 결국 어떤 경로를 제외한 모든 간선을 제거하고, 남은 경로에서 한 간선을 제거한 뒤, 남은 간선들의 가중치의 합을 총 가중치 합에서 빼주면 되는 문제입니다. 물론 그 값이 최댓값이 되어야 한다는 것이 문제지만 생각을 조금 달리 해보면 쉽게 풀 수 있습니다. 총 가중치 합 - 특정 간선의 가중치 합 을 최대로 만들어야 하는 문제인데, 총 가중치 합은 정해져 있으므로 특정 간선의 ..