1626번: 두 번째로 작은 스패닝 트리

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

MST를 이루는 간선(e1)을 하나 제거하고 그 간선과 다른 가중치의 간선(e2)으로 forest를 연결해보자. 두 번째로 작은 스패닝 트리는 (e2의 가중치) - (e1의 가중치)가 가장 작을 때 만들어 진다.

e2를 MST에 추가하면 그래프에는 정확히 하나의 사이클이 존재하고 그 사이클에 e1과 e2가 모두 존재한다. 다시 말해 MST에서 e2의 양 끝 정점을 연결하는 MST 위의 경로 중에 e1이 존재한다.

(e2의 가중치) - (e1의 가중치)의 최솟값을 구하기 위해선 MST에 없는 간선(e2)마다 트리 위의 경로 중 가중치가 해당 간선보다 작으면서 가장 큰 간선(e1)을 찾으면 된다.

이러한 문제는 LCA를 구해서 해결할 수 있는 문제로 기본적인 트릭이 잘 알려져 있다. 아래 소스에서는 sparse table을 이용하여 주어진 두 정점에 대해 LCA 및 1, 2번째 최소 가중치 간선을 $O(\lg n)$에 구할 수 있도록 구현했다. 여기서 두 개의 최소 가중치를 구하는 이유는 만약 첫 번째 최소 가중치가 e2의 가중치와 같을 경우 두 번째 가중치를 사용해야 하기 때문이다.

답은 (MST 가중치) + min( (e2의 가중치) - (e1의 가중치) )이다.

최종 시간복잡도는 $O(e\lg v)$

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct edge {
    int x, y, d;
}ed[200000];
struct st {
    int f = -1, s = -1;
    st operator+(st t) const {
        st ret = *this;
        if (ret.f^t.f) ret.s = max(ret.s, t.f);
        if (ret.f < ret.s) swap(ret.f, ret.s);
        ret.s = max(ret.s, t.s);
        return ret;
    }
}maxi[50001][16];
int v, e, par[50001], tot, dp[50001][16], lv[50001], ck[200000], cnt, res = -1;
vector<pair<int, int> > adj[50001];
int p(int x) { return x^par[x] ? par[x] = p(par[x]) : x; }
void f(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) {
        dp[it.first][0] = h;
        maxi[it.first][0].f = it.second;
        for (int i = 1; i < 16; i++) {
            dp[it.first][i] = dp[dp[it.first][i - 1]][i - 1];
            maxi[it.first][i] = maxi[dp[it.first][i - 1]][i - 1] + maxi[it.first][i - 1];
        }
        lv[it.first] = lv[h] + 1;
        f(it.first, h);
    }
}
st query(int x, int y) {
    st ret;
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = 16; i--;) if (1 << i <= lv[x] - lv[y]) ret = ret + maxi[x][i], x = dp[x][i];
    if (x == y) return ret;
    for (int i = 16; i--;) if (dp[x][i] != dp[y][i]) {
        ret = ret + maxi[x][i] + maxi[y][i];
        x = dp[x][i];
        y = dp[y][i];
    }
    return ret + maxi[x][0] + maxi[y][0];
}
int main() {
    scanf("%d%d", &v, &e);
    for (int i = 0; i < e; i++) scanf("%d%d%d", &ed[i].x, &ed[i].y, &ed[i].d);
    sort(ed, ed + e, [](edge i, edge j) {return i.d < j.d; });
    for (int i = 1; i <= v; i++) par[i] = i;
    for (int i = 0; i < e; i++) {
        int ra = p(ed[i].x), rb = p(ed[i].y);
        if (ra^rb) {
            par[ra] = rb;
            adj[ed[i].x].push_back({ ed[i].y,ed[i].d });
            adj[ed[i].y].push_back({ ed[i].x,ed[i].d });
            tot += ed[i].d;
            ck[i] = 1;
            cnt++;
        }
    }
    if (cnt^v - 1) { puts("-1"); return 0; }
    f(1, 0);
    for (int i = 0; i < e; i++) if (!ck[i]) {
        st ret = query(ed[i].x, ed[i].y);
        if (ret.f^ed[i].d && (!~res || res>ed[i].d - ret.f + tot)) res = ed[i].d - ret.f + tot;
        if (~ret.s && (!~res || res>ed[i].d - ret.s + tot)) res = ed[i].d - ret.s + tot;
    }
    printf("%d", res);
    return 0;
}

1396번: 크루스칼의 공

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

$O(n+(m+q)\lg m)$

먼저 간선 e[0...m-1]을 가중치를 기준으로 오름차순 정렬한다.
그러면 각 (from, to) 쿼리에 대해
e[0...x]를 가지고 크루스칼 알고리즘을 통해 최소신장트리를 만들었을 때 from과 to가 같은 트리에 존재하는지 판정하는 결정문제로 바꿔 이진 검색으로 해결할 수 있다.
이제 다수의 쿼리를 빠르게 풀기 위해 Parallel Binary Search를 한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct st {
    int x, y, z;
}e[100000];
int n, m, q, u[100000], v[100000], from[100000], to[100000], low[100000], up[100000], p[100001], sz[100001];
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
vector<int> mid[100000];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    sort(e, e + m, [](st l, st r) {
        return l.z < r.z;
    });
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d%d", from + i, to + i);
        low[i] = 0;
        up[i] = m - 1;
    }
    for (int i = m; i; i /= 2) {
        for (int j = 1; j <= n; j++) p[j] = j, sz[j] = 1;
        for (int j = 0; j < q; j++) mid[low[j] + up[j] >> 1].push_back(j);
        for (int j = 0; j < m; j++) {
            int x = par(e[j].x), y = par(e[j].y);
            if (x ^ y) p[y] = x, sz[x] += sz[y];
            for (auto it : mid[j]) {
                if (par(from[it]) ^ par(to[it])) low[it] = j + 1;
                else {
                    up[it] = j - 1;
                    u[it] = e[j].z;
                    v[it] = sz[x];
                }
            }
            mid[j].clear();
        }
    }
    for (int i = 0; i < q; i++) u[i] ? printf("%d %d\n", u[i], v[i]) : puts("-1");
    return 0;
}

2126번: 지진

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


$O(cm\lg m)$

시간당 최대 이득이 x이상인가를 확인하는 결정 문제로 바꿔보자.
mst를 이루는 간선들의 (ci,ti)에 대해
{f-sum(ci)}/sum(ti) >= x
정리하면 f>=sum(ci+ti*x)
우변은 잘 알려진 프림, 크루스칼 알고리즘을 통해 최솟값을 구할 수 있다.

이제 파라메트릭 서치를 할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 400, MXM = 1e4;
struct st {
    int u, v, c, t;
}e[MXM];
int n, m, f, p[MXN + 1];
double low, up, mid;
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
bool mst() {
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(e, e + m, [](st i, st j) {return i.c + i.t*mid < j.c + j.t*mid; });
    double s = 0;
    for (int i = 0; i < m; i++) if (par(e[i].u) ^ par(e[i].v)) {
        p[par(e[i].u)] = par(e[i].v);
        s += e[i].c + e[i].t*mid;
    }
    return s <= f;
}
int main() {
    scanf("%d%d%d", &n, &m, &f);
    for (int i = 0; i < m; i++) scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].c, &e[i].t);
    up = f;
    for (int i = 0; i < 100; i++) {
        mid = (low + up) / 2;
        mst() ? low = mid : up = mid;
    }
    printf("%.4lf", mid);
    return 0;
}

13418번: 학교 탐방하기

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


$O(n+m)$

가중치가 0인 간선부터 선택해서 mst를 만들 때와 1인 간선부터 선택해서 만들 때를 비교하여 0의 개수 제곱차를 구한다.

#include<cstdio>
int n, m, p[2][1001], r1, r2;
int f(int *a, int x) { return x^a[x] ? a[x] = f(a, a[x]) : x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) p[0][i] = p[1][i] = i;
    for (int i = 0, x, y, z; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        p[z][f(p[z], x)] = f(p[z], y);
    }
    r1 = n + 1;
    r2 = -1;
    for (int i = 0; i <= n; i++) r1 -= p[0][i] == i, r2 += p[1][i] == i;
    printf("%d", r1*r1 - r2*r2);
    return 0;
}

10423번: 전기가 부족해

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


$O(m\lg n+k)$

모든 발전소가 하나의 집합에 있다고 가정하고 최소신장트리를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, k, p[1001], r;
struct st {
    int x, y, z;
}e[100000];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0, t; i < k; i++) scanf("%d", &t), p[t] = 0;
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    sort(e, e + m, [](st i, st j) {return i.z < j.z; });
    for (int i = 0; i < m; i++) {
        int ra = f(e[i].x), rb = f(e[i].y);
        if (ra^rb) p[ra] = rb, r += e[i].z;
    }
    printf("%d", r);
    return 0;
}

11991번: Fenced In (Platinum)

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


$O((n+m)\lg (n+m))$

(n+1)*(m+1)개의 지점을 노드로, 인접한 선분의 길이를 인접한 노드로 이동하는데 드는 비용으로 놓으면 최소신장트리를 구해서 문제를 해결 할 수 있다.
크루스칼 알고리즘을 쓸 때 작은 비용의 간선부터 그리디하게 선택할 수 있음을 알고 있을 것이다.
같은 행, 열에 존재하는 선분 길이는 모두 같으므로 한꺼번에 최소신장트리에 포함시킬 수 있다.
이를 이용한 방법은 다음과 같다.

1. 행, 열을 구분하여 나눠진 간격을 배열에 저장하고 오름차순 정렬한다.
2. 작은 간격부터 보면서 행 간격, 열 간격 모두 등장할 때까지 해당 줄에 있는 인접한 지점 사이에 있는 선분을 제거한다.
3. 행, 열 간격이 모두 등장한 이후라면 주어진 연결된 지점들과 연결할 수 있는 최소한의 선분만 제거한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, A, B, a[25002], b[25002], ac, bc;
long long r;
pair<int, int> p[50002];
int main() {
    scanf("%d%d%d%d", &A, &B, &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) scanf("%d", b + i);
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    a[n + 1] = A;
    b[m + 1] = B;
    for (int i = 0; i <= n; i++) p[i] = { a[i + 1] - a[i],0 };
    for (int i = 0; i <= m; i++) p[i + n + 1] = { b[i + 1] - b[i],1 };
    sort(p, p + n + m + 2);
    for (int i = 0; i<n + m + 2; i++) {
        if (!ac || !bc) r += (long long)(p[i].second ? n : m)*p[i].first;
        else r += (long long)(p[i].second ? n + 1 - ac : m + 1 - bc)*p[i].first;
        p[i].second ? bc++ : ac++;
    }
    printf("%lld", r);
    return 0;
}

1197번: 최소 스패닝 트리

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


$O(e\lg v)$

#include<cstdio>
#include<algorithm>
using namespace std;
struct st {
    int x, y, z;
    bool operator < (st i) const {
        return z < i.z;
    }
}s[100000];
int v, e, p[10001], r;
int f(int x) { return x - p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d %d", &v, &e);
    for (int i = 0, x, y, z; i < e; i++) scanf("%d %d %d", &x, &y, &z), s[i] = { x,y,z };
    sort(s, s + e);
    for (int i = 1; i <= v; i++) p[i] = i;
    for (int i = 0; i < e; i++) if (f(s[i].x) != f(s[i].y)) p[f(s[i].x)] = f(s[i].y), r += s[i].z;
    printf("%d", r);
    return 0;
}

2887번: 행성 터널

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


$O(nlgn)$

최종적으로 연결된 임의의 두 행성 a,b의 비용으로 선택된 성분을 w라고 하자.( 비용은 |wa-wb| )
그렇다면 두 행성을 제외한 어떠한 행성들도 w성분이 wa, wb 사이값을 가지지 않는 경우가 해집합에 존재한다.
사이값을 가지는 행성 c가 존재할 경우, a-b 연결 대신에 a-c, c-b 연결이 항상 최선이기 때문이다.
따라서 각 성분마다 정렬을 하며, 해당 성분값이 인접한 두 행성마다 간선을 만들어주고 이 간선들을 이용해 mst를 만들면 된다.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
int n, flag[MAX_N], a[MAX_N][3], c;
long long r;
pair<int, int> p[MAX_N];
int f(int x) {
    if (x == flag[x]) return x;
    return flag[x] = f(flag[x]);
}
struct st {
    int x, y, d;
    bool operator<(st i) const {
        return d < i.d;
    }
}q[MAX_N * 3];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]), flag[i] = i;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) p[j] = { a[j][i],j };
        sort(p, p + n);
        for (int j = 0; j < n - 1; j++) q[c++] = { p[j].second,p[j + 1].second,p[j + 1].first - p[j].first };
    }
    sort(q, q + c);
    for (int i = 0; i < c; i++) {
        int ra = f(q[i].x), rb = f(q[i].y);
        if (ra ^ rb) flag[rb] = ra, r += q[i].d;
    }
    printf("%lld", r);
    return 0;
}