[백준 6497번] 전력난 C++ 풀이/해결

전력난 성공

---

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	8962	3202	2361	33.165%

 

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

 

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

---

풀이

#include<iostream>
#include<algorithm>
using namespace std;


int m, n;

pair<long, pair<int, int>> edge[200001];
int parents[200001];

long res=0;
int edgenum = 0;


int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	parents[x] = y;
}


int main()
{


	int x, y, z;


	while(1)
	{
		edgenum = 0;
		res = 0;


		cin >> m >> n;

		
		if (m == 0 && n == 0)
			break;


		for (int i = 0; i <= n; i++)
		{
			parents[i] = i;
			edge[i] = { 0,{0,0} };
		}



		for (int i = 0; i < n; i++) 
		{
			cin >> x >> y >> z;

			edge[i] = { z,{x,y} };
			res += z;

		}


		sort(edge, edge + n);


		for (int i = 0; i < n; i++)
		{
			if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
				continue;

			Merge(edge[i].second.first, edge[i].second.second);
			res -= edge[i].first;

			edgenum++;
			if (edgenum == m - 1)
				break;
		}

		cout << res<<'\n';


	}

}

 

 

위의 문제에서 입력부분을 잘 보면  "입력은 여러 개의 테스트 케이스로 구분되어 있다." 라는 말이 있습니다.

 

네, 이 말 때문에 몇번 틀렸습니다. 

저는 백준문제들의 정답비율을 낮추는데에 한번 더 공헌을 했습니다.

 

입력받는 부분을 무한반복문으로 돌리면서 0,0을 입력받으면 끝나게 해야합니다. 저는 오히려 "도시상의 모든 길의 거리 합은 231미터보다 작다." 같은 자료형 범위를 유심히 살피다가 오히려 근본적인 문제에서부터 잘못된거죠..(´。＿。｀)..

 

그래도 푸는데 따로 어려운점은 없었습니다. 바로 직전에 풀었던 최소스패닝트리와 매우 유사합니다.

 

 

 

https://www.acmicpc.net/problem/6497

6497번: 전력난