1939 - 중량제한

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

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;
}