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

4012번: 컨벤션 센터

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


$O(n\lg n)$

개구간 (l,r)에 컨벤션 센터를 이용할 수 있는 단체의 최대 개수 f(l,r)을 빠르게 구할 수 있다고 해보자.
그럼 1번 단체부터 차례대로 스케줄에 넣어 보면서 최적해를 유지하는지 빠르게 판단할 수 있다.
(스케줄 상 두 단체 사이 구간을 파악하는 일련의 연산은 map, set을 활용하여 해결할 수 있다.)

<f(l,r) 구하는 방법>
먼저, 단체를 회의 시작시간을 기준으로 오름차순 정렬하자.
x번 단체 바로 앞에 회의가 진행되었을 경우, 그 단체는 x번 단체 회의 시작 이전에 회의가 끝난 단체 중 시작 시간이 가장 늦은 단체여야 유리하다.
이러한 성질을 이용하여
dp[x][i]: x번 단체의 2^i번째 이전 단체
인 sparse table을 만들 수 있다.
그럼 r 전에 끝난 단체 중 가장 늦게 시작한 단체 p를 찾은 뒤
p의 2^i 이전 단체가 l 이후에 시작했는지 여부에 따라 p를 옮겨가며 카운트 하면 f(l,r)을 $O(\lg n)$에 구할 수 있다.

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MXN = 2e5;
int n, dp[MXN + 1][18], top = 1;
pair<int, int> stk[MXN + 1], p[MXN + 1], s[MXN + 1], e[MXN + 1];
int f(int l, int r) {
    int x = (lower_bound(stk, stk + top, make_pair(r, 0)) - 1)->second, ret = 1;
    if (p[x].first <= l) return 0;
    for (int i = 17; i >= 0; i--) if (p[dp[x][i]].first > l) x = dp[x][i], ret += 1 << i;
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);
        s[i] = { p[i].first,i };
        e[i] = { p[i].second,i };
    }
    sort(s + 1, s + 1 + n);
    sort(e + 1, e + 1 + n);
    for (int i = 1, j = 1, prv = 0; i <= n; i++) {
        for (; e[j].first < s[i].first; j++) if (p[prv].first < p[e[j].second].first) prv = e[j].second;
        while (stk[top - 1].first >= p[s[i].second].second) top--;
        stk[top++] = { p[s[i].second].second,s[i].second };
        dp[s[i].second][0] = prv;
        for (int j = 1; j < 18; j++) dp[s[i].second][j] = dp[dp[s[i].second][j - 1]][j - 1];
    }
    printf("%d\n", f(0, 2e9));
    map<int, int> mp;
    mp[0] = 0;
    mp[2e9] = 2e9;
    for (int i = 1; i <= n; i++) {
        auto l = mp.lower_bound(p[i].first), r = l--;
        if (l->second < p[i].first&&p[i].second < r->first
            &&f(l->second, r->first) == f(l->second, p[i].first) + 1 + f(p[i].second, r->first)) {
            printf("%d ", i);
            mp[p[i].first] = p[i].second;
        }
    }
    return 0;
}

2357번: 최소값과 최대값

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


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

sparse table을 이용한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
struct st {
    int l, h;
    st operator+(st i) const {
        return{ min(l,i.l),max(h,i.h) };
    }
}dp[100001][17];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        dp[i][0] = { x,x };
        for (int j = 1; 1 << j <= i; j++) dp[i][j] = dp[i][j - 1] + dp[i - (1 << j - 1)][j - 1];
    }
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        st r = { (int)1e9,0 };
        for (int i = 16; x <= y; i--) if (1 << i <= y - x + 1) r = r + dp[y][i], y -= 1 << i;
        printf("%d %d\n", r.l, r.h);
    }
    return 0;
}

11438번: LCA 2

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


$O(n+m\lg n)$

LCA를 구현하자. sparse table을 이용한다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000, LGN = 16;
int n, m;
int dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto it : adj[h]) {
        if (ck[it]) continue;
        lv[it] = lv[h] + 1;
        dp[it][0] = h;
        for (int i = 1; i <= LGN; i++)
            dp[it][i] = dp[dp[it][i - 1]][i - 1];
        dfs(it);
    }
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = LGN; i >= 0; i--)
        if (dp[x][i] != dp[y][i])
            x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}