[ boj : 235 ] 대운하

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

2350번: 대운하

문제 : 읽고오세염 ㅎㅎ

해설 : 언뜻보면 그냥 1939 이문제와 동일해 보이지만 중요한 점은 '쿼리'가 존재한다는 것 입니다.

보통 이 문제를 풀때 '오프라인 쿼리'라는 개념을 적용하여 푼다고 하는데 전 이건 모릅니다.
만약 n이 이것보다 훨씬 크다면 'small to large trick'을 사용해서 풀어야 한다고 하네요.
(관련 문제는 전 다루지 않겠습니다...전 못풀어요 ㅠ)

다시 이 문제로 돌아와서 현재 직면한 문제점은 바로 매 쿼리마다 답을 도출하는 행위입니다.
매번 탐색을 통해서 답을 구해내기에는 쿼리의 제한과 n의 제한이 크므로 O(nq)에는 절대 해결할 수 없습니다.

다른 방법을 생각해보면 우리가 답을 구하기 위해서 필요없는 간선들을 제거해봅시다. 제거하는 이유는 정점(u->v)로 가는 경로중 최소한의 간선만 남겨놓아도 충분히 답을 구할 수 있기 때문입니다.

그럼 어떤 간선들을 어떻게 제거해야될까요???
생각을 살짝만 바꿔서 정점들만이 주어지고 간선들로 연결이 되어있지 않을때 필요한 간선들만 연결하여 하나의 그래프로 만든다고 생각해보면 이는 mst 문제로 바뀌게 됩니다.

다만 여기선 minimum이 아닌 maximum 이 되겠네요.

그리고 각 쿼리에 대해서 답을 구하려고 하는 것이 아니라 mst를 만드는 과정에서 미리 답을 주르륵 구하도록 해봅시다.

집합 A와 B가 주어졌을때 두 집합을 합치면서 각 집합에 속해있던 정점들을 dist[x][y] = dist[y][x] = weight 로 저장해주면 되겠죠.(다만 전 이걸 구현하는 것이 정말 미친듯이 어려웠습니다....)

#include<bits/stdc++.h>

using namespace std;

struct info {
    int s, e, weight;
    bool operator<(const info& cur) const {
        return weight > cur.weight;
    }
};

int parent[1010];
int dist[1010][1010], memo[1010];
vector<info> v;
vector<int> adj[1010];

void show(int n);
void union_parent(int x, int y);
int get_parent(int x);
void dfs(int x, int y, int w, int p1,int p2);
void dfs2(int x, int y, int w, int p);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i <= n; i++)parent[i] = i;
    int x, y, z;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        v.push_back({ x,y,z });
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        if (get_parent(v[i].s) != get_parent(v[i].e)) {
            x = v[i].s;
            y = v[i].e;
            int w = v[i].weight;
            union_parent(x, y);

            dfs(x, y, w, -1,-1);

            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }
    int a[10000], b[10000];
    for (int i = 0; i < q; i++) 
        cin >> a[i] >> b[i];
    for (int i = 0; i < q; i++)
        cout << dist[a[i]][b[i]] << "\n";
    return 0;
}
void dfs(int x, int y, int w,int p1,int p2)
{
    dist[x][y] = dist[y][x] = w;

    for (int u : adj[y]) {
        if (p2 == u)continue;
        dfs2(x, u, w, y);
    }
    for (int u : adj[x]) {
        if (p1 == u)continue;
        dfs(u, y, w, x,-1);
    }
}
void dfs2(int x,int y,int w, int p)
{
    dist[x][y] = dist[y][x] = w;
    for (int u : adj[y]) {
        if (p == u)continue;
        dfs2(x, u, w, y);
    }
}
void union_parent(int x, int y)
{
    x = get_parent(x);
    y = get_parent(y);
    parent[x] = y;
}
int get_parent(int x)
{
    if (x == parent[x])return x;
    return parent[x] = get_parent(parent[x]);
}

저가 짠 소스이지만 직관적이지 않습니다. 해서 다른분의 소스를 첨부하겠습니다.

#include <bits/stdc++.h>
using namespace std;

short ans[1005][1005];
int p[1005];
vector<int> v[1005];
struct A {
    int a, b, w;
    bool operator<(const A &o) const {
        return w > o.w;
    }
};

int f(int x)
{
    if (p[x] != x)
        p[x] = f(p[x]);
    return p[x];
}

void g(int x, int y, int w)
{
    x = f(x);
    y = f(y);
    if (x == y)
        return;
    p[x] = y;
    for (int a : v[x])
        for (int b : v[y])
            ans[a][b] = ans[b][a] = w;
    for (int a : v[x])
        v[y].push_back(a);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k, i;
    cin >> n >> m >> k;
    vector<A> adj;
    for (i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        adj.push_back({ a, b, w });
    }
    for (i = 1; i <= n; i++)
    {
        v[i].push_back(i);
        p[i] = i;
    }
    sort(adj.begin(), adj.end());
    for (A x : adj)
        g(x.a, x.b, x.w);
    for (i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << ans[a][b] << '\n';
    }
}