백준 23034 - 조별과제 멈춰!(C++)

문제 링크입니다. https://www.acmicpc.net/problem/23034

23034번: 조별과제 멈춰!

다익스트라와 그래프 탐색을 이용한 문제입니다.

두 명의 팀장이 주어질 때, 각 팀장을 기준으로 2개의 조로 나눕니다.
이때, 모든 학생에게 공지를 전달할 떄의 최소 비용을 구하는 문제입니다.

2명의 조장에게 공지를 전달하니, 2명의 조장은 서로 연락을 통해 공지를 알릴 필요가 없습니다.
그렇다면, 2명을 연결하는 비용 중에서 가장 큰 비용을 찾고 해당 간선을 없애 2개의 조를 만든다면
가장 적은 비용으로 모든 학생에게 연결하는 방법이 될 것입니다.

일단, 모든 학생을 연결할 때의 최소 비용을 구해야 합니다.
이는 최소 스패닝 트리를 통해 쉽게 구할 수 있습니다.

문제는 2명의 조장을 잇는 비용 중, 가장 큰 비용을 찾는 것입니다.
이것을 구하기 전, 알고 있는 것은 최소 스패닝 트리를 하는 과정에서 어떤 선들이 연결됐는지 입니다.
그러면, X점과 Y점을 잇는 비용을 탐색할 수 있게 됩니다.

문제에서 Q의 값이 10,000인 것을 보아, 모든 경우마다 탐색을 하게 되면 10,000번의 탐색을 해야하지만,
모든 N개를 전부 확인할 때는 1,000번이면 구할 수 있게 됩니다.
따라서, 먼저 모든 2개의 정점들 간의 최대 비용을 구한 뒤, 최소 스패닝 트리 비용에서 빼주면 되겠습니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int N, M, Q;
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;
int parent[1001];
int check[1001][1001];
vector<pair<int, int>> line[1001];
pair<int, int> team[10001];
priority_queue<pair<int, int>> q;

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

bool cmp(info a, info b){
	if(a.cost < b.cost) return true;
	else return false;
}

int Find(int x){
	if(x == parent[x]) return x;
	else return parent[x] = Find(parent[x]);
}

void Union(int x, int y){
	parent[min(x, y)] = max(x, y);
}

void Dijstra(int st){
	for(int i = 1; i <= N; i++) check[st][i] = INF;
	check[st][st] = 0;
	q.push({-0, st});
	while(!q.empty()){
		int x = q.top().S;
		int cost = -q.top().F;
		q.pop();
		if(check[st][x] < cost) continue;
		for(int i = 0; i < line[x].size(); i++){
			int xx = line[x][i].F;
			//현재 비용과 다음 선의 비용 중, 큰 비용을 가져온다.
			int n_cost = max(cost, line[x][i].S);
			if(check[st][xx] > n_cost){
				check[st][xx] = n_cost;
				q.push({-check[st][xx], xx});
			}
		}
	}
}

void solve(){
	reset_parent();
	sort(connect.begin(), connect.end(), cmp);
	int cost = 0;
	for(int i = 0; i < connect.size(); i++){
		int x = Find(connect[i].x);
		int y = Find(connect[i].y);
		if(x != y){
			Union(x, y);
			line[connect[i].x].push_back({connect[i].y, connect[i].cost});
			line[connect[i].y].push_back({connect[i].x, connect[i].cost});
			cost += connect[i].cost;
		}
	}
	for(int i = 1; i <= N; i++){
		//i번 점에서 시작해 다른 점들까지 연결되는 선들 중, 가장 높은 비용을 찾는다.
		Dijstra(i);
	}
	for(int i = 1; i <= Q; i++){
		//두 팀장을 잇는 선들 중, 가장 비용이 큰 선을 빼고 전달한다면 그것이 최소 비용이다.
		cout << cost - check[team[i].F][team[i].S] << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect.push_back({x, y, cost});
	}
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		team[i] = {x, y};	
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.