BOJ 10169 - 안전한 비상연락망

문제 링크 : https://www.acmicpc.net/problem/10169

문제 풀이

 부분 부분 알고 있었던 내용이었다. 간선이 하나씩 없어지는데 각각의 경우에 MST 길이 합을 구하는 문제이다. 

 가장 먼저 생각할 수 있는 부분은 맨 처음에 전체 그래프에서 MST를 구해서 MST에 쓰이는 간선과 쓰이지 않는 간선을 나눌 수 있다는 것이다. 또한 거기에 더해서 첫 MST 에 쓰이지 않는 간선들은 제외를 해도 길이 합이 변하지 않는 다는 것 까지 알 수 있다. 그렇다면 첫 MST에 쓰인 간선이 지워졌을 때 대체하는 최소 비용의 간선을 모든 간선에 대해서 다 구해야 한다. 

 그 이후로는 이 문제의 경험이 굉장히 도움이 되었다. MST에 속하지 않은 간선 들은 cross edge 또는 back edge가 된다. 이때 MST에 속한 간선 E의 양 끝 노드 중 더 아래쪽 노드 p에 대해서 간선의 한 쪽 끝이 p의 서브 트리에 속해 있고, 나머지 하나는 그렇지 않은 back edge나 cross edge 들은 그 간선 E의 대체 간선이 될 수 있다. 이는 E가 사라지게 되면 전체 트리가 p의 서브 트리와 그렇지 않은 부분의 두 부분으로 쪼개지기 때문이다. 

 이를 반대로 생각해보자. MST 에 속하지 않은 간선 E는 E의 양 끝 두 노드 사이의 경로에서 LCA를 뺀 부분에 대하여 대체 간선이 될 수 있다. 그렇게 대체할 수 있다고 체크를 해두면, 나중에 트리의 각 위치에 대해서 대체 가능한 값 중 최솟값을 선택하면 되고, 이 모든 것이 트리의 경로에서 업뎃이 이루어지기 때문에 HLD+lazy segment tree 를 쓰면 된다는 결론이 나온다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll c,a,b,idx,chk;
};
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[310101];
vector<ll> v[310101];
vector<poi> nov;
ll par[310101];
vector<poi> edg;
ll in[310101];
ll out[310101];
pii tree[1010101];
long long int ans[310101];
ll dep[310101];
ll sz[310101];
ll top[310101];
vector<ll> dv[310101];
 
void dfs1(ll x){
    sz[x]=1;
    for(auto n:v[x]){
        if(sz[n]) continue;
        dep[n]=dep[x]+1;
        par[n]=x;
        dfs1(n);
        sz[x]+=sz[n];
        dv[x].push_back(n);
        if(sz[n]>sz[dv[x][0]]) swap(dv[x][0],dv[x].back());
    }
}
 
ll np;
void dfs2(ll x){
    np++;
    in[x]=np;
    for(auto k:dv[x]){
        if(dv[x][0]==k) top[k]=top[x];
        else top[k]=k;
        dfs2(k);
    }
    out[x]=np;
}
 
 
ll fi(ll x){
    if(x==par[x]) return x;
    return par[x]=fi(par[x]);
}
 
void mer(ll a,ll b){
    a=fi(a);
    b=fi(b);
    par[a]=b;
}
 
bool sf(poi a,poi b){
    return a.c<b.c;
}
 
void laz(ll s,ll e,ll nod){
    if(tree[nod].ss!=1e9){
        if(s!=e){
            tree[nod*2].ss=min(tree[nod].ss,tree[nod*2].ss);
            tree[nod*2+1].ss=min(tree[nod].ss,tree[nod*2+1].ss);
        }
        tree[nod].ff=min(tree[nod].ff,tree[nod].ss);
        tree[nod].ss=1e9;
    }
}
 
void upt(ll l,ll r,ll v,ll s,ll e,ll nod){
    if(r<s||e<l) return ;
    if(l<=s&&e<=r){
        tree[nod].ss=min(tree[nod].ss,v);
        return ;
    }
    ll m=(s+e)/2;
    upt(l,r,v,s,m,nod*2);
    upt(l,r,v,m+1,e,nod*2+1);
    return ;
}
 
ll solval;
void sol(ll idx,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(idx<s||idx>e) return ;
    if(s==e){
        solval=tree[nod].ff;
    }
    else{
        sol(idx,s,(s+e)/2,nod*2);
        sol(idx,(s+e)/2+1,e,nod*2+1);
    }
    return;
}
 
void lupt(ll a,ll b,ll v){
    while(top[a]!=top[b]){
        if(dep[top[a]] > dep[top[b]]) swap(a, b);
        ll x=top[b];
        upt(in[x],in[b],v,1,n,1);
        b=par[x];
    }
    if(dep[a] > dep[b]) swap(a, b);
    upt(in[a]+1,in[b],v,1,n,1);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f;
    cin>>n>>m;
 
    for(i=1;i<=n;i++){
        par[i]=i;
    }
 
    for(i=1;i<=m;i++){
        poi x;
        cin>>x.a>>x.b>>x.c;
        x.idx=i;
        x.chk=0;
        edg.pb(x);
    }
    sort(edg.begin(), edg.end(),sf);
 
    long long int val=0;
 
    for(auto &k:edg){
        if(fi(k.a)!=fi(k.b)){
            v[k.a].pb(k.b);
            v[k.b].pb(k.a);
            k.chk=1;
            mer(k.a,k.b);
            val+=k.c;
        }
        else{
            nov.pb(k);
        }
    }
 
    for(i=1;i<=n;i++){
        par[i]=0;
    }
 
    dep[1]=1;
    dfs1(1);
    top[1]=1;
    dfs2(1);
 
    for(i=1;i<=1010100;i++){
        tree[i].ff=1e9;
        tree[i].ss=1e9;
    }
 
    for(auto k:nov){
        lupt(k.a,k.b,k.c);
    }
 
    for(auto k:edg){
        if(!k.chk){
            ans[k.idx]=val;
        }
        else{
            ll x;
            if(dep[k.a]>dep[k.b])
                x=k.a;
            else 
                x=k.b;
 
            sol(in[x],1,n,1);
 
            if(solval>=1e9)
                ans[k.idx]=-1;
            else 
                ans[k.idx]=val-k.c+solval;
        }
    }
 
    for(i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
}