백준 11085번: 군사 이동
군사 이동
아이디어
C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다.
간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답!
코드
#include <bits/stdc++.h>
using namespace std;
typedef struct _data {
int s, e, w;
bool operator<(_data d) {
return w > d.w;
}
} Data;
int P, W, C, V;
int p[1000];
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
p[n1] += p[n2];
p[n2] = n1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> P >> W;
cin >> C >> V;
vector<Data> v;
for (int i = 0; i < W; i++) {
int s, e, w;
cin >> s >> e >> w;
v.push_back({s, e, w});
}
memset(p, -1, sizeof(p));
sort(v.begin(), v.end());
for (auto d : v) {
Union(d.s, d.e);
if (find(C) == find(V)) {
cout << d.w;
break;
}
}
return 0;
}
여담
문제 뭔소린지 이해 안돼서 한참 읽었다. 난 붕어다.
Author And Source
이 문제에 관하여(백준 11085번: 군사 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-11085번-군사-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)