문제 풀이 모든 두 집 쌍에 대해서 불이 켜진 길로만 서로를 왕래할 수 있도록 해야 하며, 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하는 문제입니다. 모든 두 집 쌍에 대해서 가로등을 켜면서(연결하면서) 최소의 비용으로 만들고 싶다면 MST를 구하라는 문제입니다. 그런데 절약할 수 있는 최대 액수를 물었으므로 [전체의 비용 - MST를 만드는 비용 = 최대 액수]로 구해주면 됩니다. 최종 비용을 계산할 때 보통은 최소의 비용을 구하라고 하지만 반대로 얼마큼 절약할 수 있는지를 물어보는 문제였습니다. 소스 코드 #include #include #include using namespace std; const int MAX = 200001; int parent[MAX]; vector edges; in..