[BOJ/Platinum 5] 백준 23034 조별과제 멈춰!(C++)

문제 링크

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

23034번: 조별과제 멈춰!

 

문제

교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 학생은 1~N의 정수 중 고유한 번호를 학번으로 갖는다.

모든 것이 귀찮은 아리는 각 조의 팀장에게만 공지를 전달한다. 아리는 N명의 학생 사이에 있는 총 M개의 회선의 리스트를 가지고 있다. 리스트에는 각 회선에 연결된 두 학생의 학번 A와 B, 연락에 필요한 비용 C가 적혀있다. 회선이 연결된 두 학생은 서로 연락이 가능하다. 아리가 각 팀장에게 공지를 전달하면, 각 팀장과 공지를 알게 된 팀원은 같은 조의 모든 팀원에게 공지 내용을 회선을 통해서만 전달한다. 어떤 학생이 팀장이 되어도 모든 학생은 공지 내용을 전달받을 수 있다.

아리는 공지 채팅방을 만들 생각은 안 하고, 모든 학생이 공지 내용을 알게 될 때까지 학생들이 연락하며 소요되는 비용의 총합 T의 최솟값을 알고 싶어졌다. 그것을 구하여 팀장을 정한 뒤 조를 구성하려고 한다.

아리는 다음과 같은 Q개의 질문을 한다.

• X Y : X와 Y가 팀장일 때, T의 최솟값은 무엇인가?

Q개의 질문에 답할 수 있는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(2 ≤ N ≤ 1,000), M(N ≤ M ≤ 100,000)가 주어진다.

다음 줄부터 M개의 줄에 세 정수 A(1 ≤ A ≤ N), B(1 ≤ B ≤ N), C(1 ≤ C ≤ 100,000)가 주어진다. A와 B가 같은 경우는 주어지지 않으며, 두 학생에 대한 회선은 여러 개가 주어지지 않는다.

다음 줄에 Q(1 ≤ Q ≤ 10,000)가 주어진다.

다음 줄부터 Q개의 줄에 두 정수 X(1 ≤ X ≤ N), Y(1 ≤ Y ≤ N)가 주어진다. X와 Y가 같은 경우는 주어지지 않는다.

출력

Q개의 질문에 대한 T의 최솟값을 출력한다.

예제 입력 1

4 4
1 2 3
1 3 4
2 3 1
3 4 7
3
1 2
3 4
2 3

예제 출력 1

8
4
10

알고리즘 분류

• 그래프 탐색
• 크루스칼 알고리즘

풀이

최소 스패닝 트리를 만들고, 최소 스패닝 트리에 속하는 간선 중 X, Y 두 팀장을 잇는 간선 중 가중치가 최대인 값을 빼면 두 팀장이 모두에게 공지 내용을 최소의 비용으로 알릴 수 있을 것이다.

다만, Q가 최대 10,000이므로, 최대 10,000번 BFS를 실행한다면 시간 제한을 넘을 것이므로, 미리 N번(최대 1,000) BFS를 실행하여, i번에서 Next번 학생으로 가는 간선의 가중치 중 최댓값을 기록해둔다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e18

using namespace std;
struct INFO {
	int Start, End;
	LL Cost;
};

struct INFO2 {
	int Dest;
	LL Cost;
	bool checked;
};

int N, M, Q;
vector<INFO> Edge;
vector<INFO2> Vec[MAX];
int Parent[MAX];
LL Far[MAX][MAX];
bool visited[MAX];
LL answer = 0;

void Init1() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
	}
}

void Init2() {
	for (int i = 1; i <= N; i++) {
		visited[i] = false;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

void Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int U = Edge[i].Start;
		int V = Edge[i].End;
		LL C = Edge[i].Cost;
		if (Find(U) != Find(V)) {
			Union(U, V);
			answer += C;
			for (int j = 0; j < Vec[U].size(); j++) {
				if (Vec[U][j].Dest == V) {
					Vec[U][j].checked = true;
					break;
				}
			}
			for (int j = 0; j < Vec[V].size(); j++) {
				if (Vec[V][j].Dest == U) {
					Vec[V][j].checked = true;
					break;
				}
			}
		}
	}
}

void BFS(int X) {
	queue<int> Q;
	visited[X] = true;
	Q.push(X);

	while (!Q.empty()) {
		int Cur = Q.front();
		Q.pop();

		for (int i = 0; i < Vec[Cur].size(); i++) {
			int Next = Vec[Cur][i].Dest;
			LL nCost = Vec[Cur][i].Cost;
			bool checked = Vec[Cur][i].checked;
			if (!visited[Next] && checked) {
				visited[Next] = true;
				Far[X][Next] = max({ Far[X][Next], Far[X][Cur], nCost });
				Q.push(Next);
			}
		}
	};
}

void Find_Answer() {
	while (Q--) {
		int X, Y;
		cin >> X >> Y;
		cout << answer - Far[X][Y] << "\n";
	};
}

void Input() {
	cin >> N >> M;
	Init1();
	for (int i = 0; i < M; i++) {
		int A, B;
		LL C;
		cin >> A >> B >> C;
		Edge.push_back({ A,B,C });
		Vec[A].push_back({ B,C,false });
		Vec[B].push_back({ A,C,false });
	}
	Settings();
	for (int i = 1; i <= N; i++) {
		Init2();
		BFS(i);
	}
	cin >> Q;
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}