[백준 23034] 조별과제 멈춰!

문제

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

 

알고리즘

MST

 

풀이

MST에서 간선을 끊는 문제입니다.

 

조장끼리는 연락을 할 필요가 없으므로 MST에서 각 조장을 잇는 최대 간선을 끊는 문제입니다. 쿼리가 1만 개 주어지므로 미리 $N$명의 사람마다 $i$에서 $j$로 연락할 때 사용하는 최대 간선을 저장해놓으면 됩니다. 이는 $N^2$에 해결 가능하므로 쿼리마다 MST를 구성하기 위한 최소 cost에서 $dist[i][j]$를 빼주면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e3 + 5;
const int MAXM = 1e5 + 5;

#define int long long

typedef pair<int, int> pii;
struct edge {
    int u, v, c;
    bool operator<(const edge& a) const {
        return c < a.c;
    }
} arr[MAXM];

vector<pii> adj[MAXN];
int N, M, Q, mc;
int p[MAXN], dist[MAXN][MAXN];

int find(int x) {
    return p[x] < 0 ? x : p[x] = find(p[x]);
}

void bfs(int here) {
    bool visited[MAXN] {};
    visited[here] = true;
    queue<int> q;
    q.emplace(here);
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (auto [there, cost] : adj[h]) {
            if (!visited[there]) {
                dist[here][there] = max({dist[here][there], dist[here][h], cost});
                visited[there] = true;
                q.emplace(there);
            }
        }
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    memset(p, -1, sizeof(p));

    cin >> N >> M;
    rep(i, M) {
        cin >> arr[i].u >> arr[i].v >> arr[i].c;
    }
    sort(arr, arr + M);
    rep(i, M) {
        auto [u, v, c] = arr[i];
        int pu = find(u);
        int pv = find(v);
        if (pu ^ pv) {
            mc += c;
            p[pu] = pv;
            adj[u].emplace_back(v, c);
            adj[v].emplace_back(u, c);
        }
    }
    REP(i, N) {
        bfs(i);
    }
    cin >> Q;
    while (Q--) {
        int u, v;
        cin >> u >> v;
        cout << mc - dist[u][v] << '\n';
    }
    return 0;
}