문제 링크
문제
가희는 도시 시뮬레이션 게임을 하고 있습니다. 이 게임은 나의 도시와 다른 도시들을 연합하여, 나의 도시를 키우는 게임입니다. 가희의 도시에 사는 사람들은 철도만 이용하여 이동합니다. 건설된 철도 노선들을 적절히 이용하여 가희의 도시에서 도시 로 이동하지 못하면, 사람들은 도시 와 교류를 하지 못하게 되고, 가희의 도시는 도시 와 연합할 수 없습니다.
가희는 월드에 있는 도시 개와 가희의 도시를 연합하여 세력을 확장하려고 합니다. 이 게임은 철도 노선 개를 구매할 수 있습니다. 가희는 이 철도 노선들을 적절하게 구매하여 총 건설 비용을 최소로 하려고 합니다. 그러면서 가희의 도시와 개의 도시들을 빠르게 연합하려고 합니다. 가희가 건설할 수 있는 철도 노선들에 대한 정보가 주어졌을 때, 총 건설 비용과 언제 개의 도시들과 가희의 도시가 연합하는지 구해주세요. 목표를 달성하는 것이 불가능하다면 첫 줄에 -1을 출력해 주세요.
입력
첫 번째 줄에 과 가 공백으로 구분되어 주어집니다. 월드에 1번 도시부터 번 도시까지 있음을 의미하며, 가희의 도시는 1번 도시입니다. 또한 건설할 수 있는 노선은 개가 있음을 의미합니다.
다음 개의 줄에 건설할 수 있는 철도 노선의 정보가 아래와 같이 주어집니다.
이는 월드에 있는 두 도시, 번 도시에서 번 도시를 경유하는 도시 없이, 양방향으로 연결하는 철도를 비용 c 를 들여 시각 에 지을 수 있음을 의미합니다. (1 ≤ from ≤ n, 1 ≤ to ≤ n, from ≠ to) 철도 노선들은 구매하는 즉시 지어지며, 같은 시각에 여러 철도 노선을 건설할 수 있습니다.
출력
가희의 도시와 개의 도시가 연합을 하는 시점과 총 건설 비용을 공백으로 구분하여 출력해 주세요. 만약, 개의 도시와 가희의 도시가 연합할 수 없다면, 첫 줄에 -1을 출력해 주세요.
제한
- 2 ≤ n ≤ 2⋅10^5
- 1 ≤ Q ≤ 2⋅10^5
- 1 ≤ time ≤ 10^9
- 1 ≤ cost ≤ 10^9
예제 입력 1
4 5
1 4 1 5
2 3 1 1000000000
1 4 1 13
3 2 1 117
2 4 1 10
예제 출력 1
117 3
3개의 도시와 연합하기 위해서, 아래와 같이 철도 노선을 건설하면 됩니다.
- 시각 5에 도시 1과 4를 연결하는 철도 노선을 비용 1을 들여 건설합니다. (그림 1의 2)
- 시각 10에 도시 2와 4를 연결하는 철도 노선을 비용 1을 들여 건설합니다. (그림 1의 3)
- 시각 117에 도시 3과 2를 연결하는 철도 노선을 비용 1을 들여 건설합니다.
이 때, 시각 117에 총 건설 비용 3을 들여, 3개의 도시와 연합할 수 있습니다. 시각 117에 건설하지 않고, 시각 1,000,000,000에 도시 2와 3을 연결하는 철도 노선을 건설하는 경우 총 건설 비용은 3입니다. 하지만 시각 117에 같은 비용을 들여 목표를 달성하는 방법이 있으므로 답이 아닙니다.
예제 입력 2
2 2
1 2 5 1
2 1 3 2
예제 출력 2
2 3
시각 1에 도시 1과 2를 잇는 철도를 비용 5를 들여서 지을 수 있습니다. 또한, 시각 2에 도시 2와 1을 잇는 철도를 비용 3을 들여서 지을 수 있습니다. 시각 1에 도시 1과 2를 잇는 철도를 건설하여, 1개의 도시와 연합할 수 있습니다. 하지만, 총 건설 비용이 최소가 아니므로 답이 되지 않습니다. 시각 2에 3의 비용을 들여서 건설하는 것이 답이 됩니다.
예제 입력 3
5 1
1 4 5 7
예제 출력 3
-1
5개의 도시가 있습니다. 시각 7에 도시 1에서 4를 연결하는 철도 노선을 비용 5를 들여 건설할 수 있습니다. (그림 2의 오른쪽) 그 이후에 건설할 수 있는 철도 노선이 없습니다. 따라서 도시 1은 도시 2, 3, 5와 연합을 하지 못하게 됩니다. 따라서 -1을 출력합니다.
알고리즘 분류
- 크루스칼 알고리즘
풀이
Q개의 노선을 Cost를 기준으로 오름차순 정렬한다. Cost가 같다면 Time을 기준으로 오름차순 정렬한다.
정렬된 Q개의 노선을 순서대로 탐색하면서 From과 To가 아직 이어지지 않았다면 두 도시를 연합한다.
연합하는 알고리즘은 분리 집합을 이용하여, 번호가 더 높은 도시의 Parent를 번호가 더 낮은 도시로 초기화한다. 이렇게 되면 최종적으로 모든 도시의 Parent는 1, 즉 가희의 도시가 된다.
두 도시를 연합하는 과정에서 Cost를 계속 누적하고, 이 시점에서 임의의 수 K개의 도시가 연합했을 때의 시각은 K개의 노선 중에서 가장 높은 Time이 된다.
Q개의 노선을 전부 탐색한 후 마지막으로 N - 1개의 도시가 가희의 도시와 연합했는지 확인하고, 모든 도시가 연합되었다면 Time과 Cost를 공백을 기준으로 출력한다. 모든 도시가 연합되지 않았다면 -1을 출력한다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 200001
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
using namespace std;
struct EDGE {
int From, To;
LL Cost, Time;
};
int N, Q, From, To;
LL Cost, Time;
vector<EDGE> Edge;
int Parent[MAX];
LL Answer_Time, Answer_Cost;
void init() {
for (int i = 0; i < MAX; i++) {
Parent[i] = i;
}
}
void input() {
cin >> N >> Q;
for (int i = 0; i < Q; i++) {
cin >> From >> To >> Cost >> Time;
Edge.push_back({ From,To,Cost,Time });
}
}
bool Comp(EDGE A, EDGE B) {
if (A.Cost == B.Cost) {
return (A.Time < B.Time);
}
return (A.Cost < B.Cost);
}
int find_Parent(int X) {
if (Parent[X] == X) {
return X;
}
return Parent[X] = find_Parent(Parent[X]);
}
void union_Group(int X, int Y) {
int ParentX = find_Parent(X);
int ParentY = find_Parent(Y);
if (ParentX < ParentY) {
Parent[ParentY] = ParentX;
}
else {
Parent[ParentX] = ParentY;
}
}
void settings() {
sort(Edge.begin(), Edge.end(), Comp);
for (int i = 0; i < (int)Edge.size(); i++) {
int Now_From = Edge[i].From;
int Now_To = Edge[i].To;
LL Now_Cost = Edge[i].Cost;
LL Now_Time = Edge[i].Time;
if (find_Parent(Now_From) != find_Parent(Now_To)) {
union_Group(Now_From, Now_To);
Answer_Cost += Now_Cost;
Answer_Time = max(Answer_Time, Now_Time);
}
}
}
bool union_Cities() {
for (int i = 2; i <= N; i++) {
if (find_Parent(i) != 1) {
return false;
}
}
return true;
}
void find_Answer() {
if (union_Cities()) {
cout << Answer_Time << " " << Answer_Cost << "\n";
}
else {
cout << "-1\n";
}
}
int main() {
FASTIO
init();
input();
settings();
find_Answer();
return 0;
}
'BOJ > Gold' 카테고리의 다른 글
[BOJ/Gold 4] 백준 28333 화이트 칼라(C++) (0) | 2024.01.23 |
---|---|
[BOJ/Gold 4] 백준 29703 펭귄의 하루(C++) (0) | 2024.01.22 |
[BOJ/Gold 5] 백준 27172 수 나누기 게임(C++) (0) | 2024.01.16 |
[BOJ/Gold 5] 백준 30470 호반우가 학교에 지각한 이유 3(C++) (1) | 2024.01.15 |
[BOJ/Gold 3] 백준 29618 미술 시간(C++) (2) | 2024.01.12 |