S에서 E로 가는 데, 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 구한다.
문제를 읽고 왠지 이거 다익스트라처럼 그리디하게 풀면 풀리겠다 싶어서 그래프 몇개 끄적거렸는데 무한루프에 빠질것만 같은 공포에 휩싸였다.
dp를 적용하자니 다리의 중량제한 \(c(1 \le c \le 10^9)\) 라서 안되겠다싶었고.
그럼 스패닝 트리를 만들어볼까해서 프림을 생각했는데 몇 개 적어놨던 예제에서부터 안됐다.
그래도 트리로 만드는게 가장 정답같아서 크루스칼로 구현했는데 정답이었다.
크루스칼로 최대 스패닝 트리를 만들고, S에서 E로 가는 경로 중에 가장 중량제한이 작은 것을 출력한다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef pair<int,int> ii;
struct edge {
int u, v, d;
bool operator < (const edge& e) const {
return d < e.d;
}
};
vector<edge> E;
int group[100001];
int find(int v){
if(v != group[v])
return (group[v] = find(group[v]));
return v;
}
bool Union(int p, int q){
p = find(p);
q = find(q);
if(p == q) return false;
group[q] = p;
return true;
}
vector<ii> adj[100001];
bool visit[100001];
int answer(int pos, int dst, int m = INF){
if(pos == dst) return m;
if(visit[pos]) return 0;
visit[pos] = true;
for(auto& v : adj[pos]){
int r = answer(v.first, dst, min(v.second, m));
if(r != 0) return r;
}
return 0;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
E.push_back({a-1, b-1, c});
}
sort(E.rbegin(), E.rend());
for(int i=0; i<n; ++i) group[i] = i;
for(auto& e : E){
if( Union(e.u, e.v) ){
adj[e.u].push_back(ii(e.v, e.d));
adj[e.v].push_back(ii(e.u, e.d));
}
}
int src, dst;
scanf("%d %d", &src, &dst);
printf("%d", answer(src-1, dst-1));
return 0;
}
다른 사람들 정답 코드를 보니까 다익스트라도 있었는데, 크루스칼로 푼 사람들 중에 하나를 보고 배웠다.
S에서 E로 가는 경로를 다시 탐색할 필요가 없이, S가 속한 집합과 E가 속한 집합이 같아지는 시점에 연결하는 간선의 중량이 "가능한 가장 큰 중량제한"이었다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef pair<int,int> ii;
struct edge {
int u, v, d;
bool operator < (const edge& e) const {
return d < e.d;
}
};
vector<edge> E;
int group[100001];
int find(int v){
if(v != group[v])
return (group[v] = find(group[v]));
return v;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
E.push_back({a-1, b-1, c});
}
sort(E.rbegin(), E.rend());
for(int i=0; i<n; ++i) group[i] = i;
int src, dst;
scanf("%d %d", &src, &dst);
for(auto& e : E){
group[find(e.u)] = find(e.v);
if( find(src-1) == find(dst-1) ){
printf("%d", e.d);
break;
}
}
return 0;
}