2017년 7월 22일 토요일

10637 Minimum Spanning Tree

10637 Minimum Spanning Tree https://www.acmicpc.net/problem/10637

1626 두 번째로 작은 스패닝 트리 문제와 유사하다.
https://lyzqm.blogspot.kr/2017/07/1626.html

그래프 $G$가 $m_{i}$의 간선들로 이루어져있을 때 각각의 $m_{i}$에 대해서 해당 간선이 존재하지 않을때 
MST의 값을 구하는 문제이다.

처음에 떠오른 생각은 우선 MST를 만든후 $m_{i}$가 트리 간선인 경우 해당 간선을 지우고 
트리간선이 아닌 다른간선으로 대체하는 방안을 떠올렸다.
($m_{i}$가 트리간선이 아닌경우는 MST값이 나올것이다.)
트리간선이 제거되는 경우 위 그림과 같이 두개의 component로 분리된다.
component를 연결하는 최소의 값을 지닌 회색 간선이 트리간선을 대체할 수 있을 것이다.
(검정색 - 트리간선, 회색 - 트리간선이 아닌 간선(일반간선으로 칭함))

문제는 어떻게 하느냐 인데 1626문제에서 처럼 LCA를 이용한다.
대신 일반 간선의 입장에서 생각해야한다.
이 간선은 {$u,v$}정점을 가리킬때 $u$에서 $v$로 가는 모든 MST 간선을 대체 할 수 있게 된다.

해당 일반간선이 MST간선을 대체할 수 있더라도 더 작은 일반 간선에 의해 대체 가능할 수 도 
있기 때문에 작은 일반간선부터 대체 가능한 MST 간선을 정해놓아야 한다.

따라서 $m_{i}$가 {$u,v$}일 때 {$u, LCA$}, {$LCA, v$}의 아직 대체 되지 않은 MST간선을 구해서 갱신해주면 된다.

하지만 이 갱신작업을 depth를 한칸 한칸씩 내리며 찾는다면 TLE가 나온다.
따라서 중복되지 않도록 최적화를 시켜줘야 하는데 다음과 같은 방법을 사용하였다.
위와 같이 붉은 선은 이미 갱신되었고 $u$에서 $LCA$로 이동한다고 한다면 
이미 갱신된 트리간선은 갈 필요가 없다.
그러므로 갱신될때마다 경로를  $LCA$로 변경시켜 주면 된다.
(추가적인 갱신조건은 코드를 참고)

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int N, M;
int par[100001], rrank[100001], depth[100001];
int pr[100001];
int edge[200001];
ll ans[200001];
int pprev[100001][21];
bool isMSTedge[200001];
pair<ll, pair<intpair<intint>>> adj[200001];    //(d, index, u, v)
ll adj_copy[200001];
vector<pair<ll, pair<intint>>> adj_mst[100001];        //u - (d, index, v)
pair<ll, pair<int,int>> adj_n_mst[200001];        //MST아닌 간선 (d, u, v)
void init() {
    memset(depth, -1sizeof depth);
    for (int n = 0;n < M;n++) ans[n] = -1;
    for (int n = 1;n <= N;n++
        par[n] = n, rrank[n] = 0;
}
int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}
bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    if (rrank[u] > rrank[v]) swap(u, v);
    else if (rrank[u] == rrank[v]) rrank[v]++;
    par[u] = v;
    return true;
}
void dfs(int here) {
    for (auto n : adj_mst[here]) {
        int next = n.second.second;
        if (depth[next] == -1) {
            int idx = n.second.first;
            depth[next] = depth[here] + 1;
            pprev[next][0= here;
            pr[next] = here;
            edge[next] = idx;
            dfs(next);
        }
    }
}
void preprocess() {
    for (int j = 1;j < 21;j++) {
        for (int i = 1;i <= N;i++) {
            pprev[i][j] = pprev[pprev[i][j - 1]][j - 1];
        }
    }
}
int getLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 20;i >= 0;i--) {
        if (depth[u] - depth[v] >= (1 << i))
            u = pprev[u][i];
    }
    if (u == v) return u;
    for (int i = 20;i >= 0;i--) {
        if (pprev[u][i] != pprev[v][i])
            u = pprev[u][i], v = pprev[v][i];
    }
    return pprev[u][0];
}
int main() {
    scanf("%d%d"&N, &M);
    init();
    for (int m = 0;m < M;m++) {
        int u, v, d;
        scanf("%d%d%d"&u, &v, &d);
        adj[m] = { (ll)d,{m,{u,v} } };
        adj_copy[m] = (ll)d;
    }
    sort(adj, adj + M);
    ll mst_val = 0;
    int mst_cnt = 0;    //
    int n_mst_cnt = 0;
    for (int m = 0;m < M;m++) {
        ll d = adj[m].first;
        int u = adj[m].second.second.first, v = adj[m].second.second.second;
        if (merge(u, v) && mst_cnt < N - 1) {        //서로다른 집합인 경우 - MST
            int idx = adj[m].second.first;
            isMSTedge[idx] = true;
            adj_mst[u].push_back({ d, { idx, v } });
            adj_mst[v].push_back({ d, { idx, u } });
            mst_val += d;
            ++mst_cnt;
        }
        else {        //MST아닌 간선
            adj_n_mst[n_mst_cnt] = { d,{u,v} }, ++n_mst_cnt;
        }
    }
    if (mst_cnt != N - 1) {
        for (int m = 0;m < M;m++printf("-1\n");
        return 0;
    }
    depth[1= 0;
    dfs(1);
    preprocess();        //2^K의 자식노드 전처리
    int cnt = 0;
    sort(adj_n_mst, adj_n_mst + n_mst_cnt);
    for (int m = 0;m < n_mst_cnt;m++) {        //MST 간선이 아닌 간선들
        ll d = adj_n_mst[m].first;
        int u = adj_n_mst[m].second.first, v = adj_n_mst[m].second.second;
        int lca = getLCA(u, v);
        if (lca != u) {
            while (1) {        // path(u, lca)
                int idx = edge[u];
                if (ans[idx] == -1) {
                    cnt++;
                    ans[idx] = mst_val + d - adj_copy[idx];
                }
                int tmp_u = u;
                u = pr[u];
                if (depth[lca] < pr[tmp_u])
                    pr[tmp_u] = lca;
                if (depth[lca] >= depth[u]) break;
            }
        }
        if (lca != v) {
            while (1) {        // path(v, lca)
                int idx = edge[v];
                if (ans[idx] == -1) {
                    cnt++;
                    ans[idx] = mst_val + d - adj_copy[idx];
                }
                int tmp_v = v;
                v = pr[v];
                if (depth[lca] < pr[tmp_v])
                    pr[tmp_v] = lca;
                if (depth[lca] >= depth[v]) break;
            }
        }
        if (cnt == mst_cnt) break;
    }
    for (int m = 0;m < M;m++) {
        if (!isMSTedge[m]) printf("%lld\n", mst_val);        //mst가 아닌 간선 - 변함없음
        else printf("%lld\n", ans[m]);
    }
    return 0;
}
cs

댓글 없음:

댓글 쓰기