[백준] 1626 - 두 번째로 작은 스패닝 트리 (c++)

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

 

문제 요약

입력으로 가중치가 있는 그래프가 주어진다. 두 번째로 작은 스패닝 트리의 값을 출력해라.

 

풀이 (MlogM)

• MST
• 희소배열
• LCA

 MST 하나를 구성하고 간선을 하나씩 대체하는 문제인 것은 빠르게 눈치 챘다. 모든 간선을 한 번씩 넣어보면서 생기는 사이클의 간선 중 하나를 빼는 것이다. 어떤 간선을 대체하냐가 문제인데 최대간선만 대체하면 항상 두 번째로 작은 스패닝 트리를 만들 수가 없다. 최대간선과 두번째로 큰 간선까지 대체해보면 답을 구할 수 있다. 대체하는 비용은 LCA,최대간선,두번째로 큰 간선을 각각 저장하는 희소배열을 하나씩 만들어서 logN으로 최적화할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct Djs {
    vector<int> p;
    Djs(int size) {
        p.resize(size);
    }
    int find(int a) {
        if (!p[a])
            return a;
        return p[a] = find(p[a]);
    }
    void Union(int a, int b) {
        p[find(a)] = find(b);
    };
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    vector<array<int,3>> ed(m),sed;
    for(auto&[c,u,v]:ed)
        cin>>u>>v>>c;
    sed=ed;
    sort(sed.begin(),sed.end());
    ll mst=0,mcnt=0;
    Djs djs = Djs(n+1);
    vector<vector<array<int,2>>> adj(n+1);
    for(auto&[c,u,v]:sed) {
        if(djs.find(u)!=djs.find(v)) {
            mcnt++;
            djs.Union(u,v);
            adj[u].push_back({c,v});
            adj[v].push_back({c,u});
            mst+=c;
        }
    }
    if(mcnt<n-1)    
        return cout<<-1,0;
    vector<int> lv(n+1);
    vector<vector<int>> sp(n+1,vector<int>(25)),smx(n+1,vector<int>(25,-1)),smx2(n+1,vector<int>(25,-1));
    auto dfs = [&](int u,auto f) -> void {
        for(auto&[c,v]:adj[u])if(!lv[v])
            lv[v]=lv[u]+1,sp[v][0]=u,smx[v][0]=c,f(v,f);
    };
    lv[1]=1;
    dfs(1,dfs);
    for(int j=1;j<25;j++)
        for(int i=1;i<=n;i++) {
            int a=smx[i][j-1],b=smx[sp[i][j-1]][j-1];
            smx[i][j]=max(a,b);
            if(a==b)
                smx2[i][j]=-1;
            else
                smx2[i][j]=min(a,b);
            sp[i][j]=sp[sp[i][j-1]][j-1]; 
        }
    ll mn=1e18,ans=1e18;

    for(auto&[c,u,v]:ed) {
        if(lv[u]<lv[v])
            swap(u,v);
        int mx=-1,mx2=-1;
        int dif=lv[u]-lv[v];
        for(int i=0;i<25;i++,dif>>=1)
            if(dif&1) {
                if(smx[u][i]>mx)
                    mx2=mx,mx=smx[u][i];
                else if(smx[u][i]<mx&&smx[u][i]>mx2)
                    mx2=smx[u][i];
                if(smx2[u][i]<mx&&smx2[u][i]>mx2)
                    mx2=smx2[u][i];
                u=sp[u][i];
            }
        if(u==v) {
            int co = mst-mx+c;
            if(co<mn)
                ans=mn,mn=co;
            else if(co>mn&&co<ans)
                ans=co;
            //cout<<mx2<<'\n';
            if(~mx2) {
                co=mst-mx2+c;
                //cout<<mx2<<' '<<mn<<' '<<ans<<'\n';
                if(co>mn&&co<ans)
                    ans=co;
            }
            continue;
        }
        for(int i=24;i>=0;i--)
            if(sp[u][i]!=sp[v][i]) {
                vector<int> ve{smx[u][i],smx2[u][i],smx[v][i],smx2[v][i]};
                for(int x:ve) {
                    if(!~x)continue;
                    if(x>mx)
                        mx2=mx,mx=x;
                    else if(x<mx&&x>mx2)
                        mx2=x;
                }
                u=sp[u][i],v=sp[v][i];
            }
        vector<int> ve{smx[u][0],smx2[u][0],smx[v][0],smx2[v][0]};
        for(int x:ve) {
            if(!~x)continue;
            if(x>mx)
                mx2=mx,mx=x;
            else if(x<mx&&x>mx2)
                mx2=x;
        }
        ll co = mst-mx+c;
        if(co>mst)
            ans=min(ans,co);
        co=mst-mx2+c;
        if(~mx2&&co>mst)
            ans=min(ans,co);
    }
    if(ans==1e18)
        ans=-1;
    cout<<ans;
}