裏紙

ほぼ競プロ、たまに日記

CF 835 F - Roads in the Kingdom

問題

Problem - F - Codeforces

問題概要

n頂点n辺の無向グラフが与えられる。辺iは頂点u_iv_iを結ぶ長さl_iの辺である。

このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。

このグラフから連結性を保ちつつ1つだけ辺を取り除く時の取り除いた後のグラフにおけるincovenienceの最小値を求めよ。

  • 3 \le n \le 200000
  • 1 \le l_i \le 10^9
  • 多重辺、自己ループは存在しない
  • 1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される

イデア

入力の条件から、「1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される」ということは、取り除いた後のグラフはn頂点n-1辺で、全体が連結ということになるので、これは木である。つまり、与えられるグラフは木に1本だけ余計な辺を足した形になっていることが分かる。

そして、そのようなグラフではループが1つだけ存在し、それに木をいくつかくっつけたような形になっているとみることができ、今回の問題で取り除く対象にできるのはこのループ内の辺に限られることになる。あとは、このループ内の辺に対して削除対象を動かしながらその時のinconvenienceを高速に計算したい。

また、inconvenienceを考える時に、我々が最小化出来るものは「ループ内の辺を通る」パスについてしか出来ないので、それの最小化を考えることにする(例えば、ループ外に巨大な木がくっついていたら、その木の中同士の頂点が最大をとるペアになりそうだが、これはどうしようもないので考えない)。この最小化を考えて、取り除く辺を決定したら、取り除かれたグラフ上で木の直径を求めれば良い。

以下、考えやすいようにループの大きさをCとして、頂点に通し番号をふってあるものとして考える。ループだけを考えれば良いようにするためにループ内の頂点に次のようなパラメータを持たせる:

  • d_i : 頂点iに対してくっついている木の中の最も遠い頂点との距離

また、次のような値を計算しておく:

  • w_i : 頂点ii+1の間の辺の重み
  • pred_i : 頂点0,1, \ldots , iの間で最も離れたペアの距離
  • sufd_i : 頂点i,i+1, \ldots , C-1の間で最も離れたペアの距離
  • pref_i : 頂点0,1, \ldots , iの間で、頂点0と最も離れた頂点の距離
  • suff_i : 頂点i,i+1, \ldots , C-1の間で、頂点0と最も離れた頂点の距離

これらを事前に計算しておくと、頂点ii+1の間の辺を切った場合のinconvenienceはmax( pref_i + suff_{i+1} , pred_i , sufd_{i+1} )で表せるので、全体でO(n)で求められる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct edge{int to; ll cost;};

const int N = 200000;
vector<edge> G[N];
int par[N];
int vis[N]={};

vector<int> cycle;
bool is_cycle[N]={};
void find_cycle(int x){
    int now = x;
    while(1){
        cycle.pb(now);
        is_cycle[now] = true;
        for(const auto &e:G[now]){
            if(e.to!=par[now] && vis[e.to]==2){
                now = e.to;
                break;
            }
        }
        if(now == x) break;
    }
}

void dfs(int x){
    vis[x] = 2;
    for(const auto &e:G[x])if(e.to != par[x]){
        if(vis[e.to]==0){
            par[e.to] = x;
            dfs(e.to);
        }
        else if(vis[e.to]==2) find_cycle(e.to);
    }
    vis[x] = 1;
}

using pi = pair<int,int>;
using P = pair<ll,pi>;

const ll INF = LLONG_MAX/3;

pair<ll,int> farthest(int start, int n){
    vector<ll> d(n, INF);
    d[start] = 0;
    queue<int> que;
    que.push(start);
    while(!que.empty()){
        int now = que.front();
        que.pop();
        for(const auto &e:G[now]){
            if(d[e.to] > d[now]+e.cost){
                d[e.to] = d[now]+e.cost;
                que.push(e.to);
            }
        }
    }

    ll max_d = 0;
    int idx = -1;
    rep(i,n){
        if(d[i] > max_d){
            max_d = d[i];
            idx = i;
        }
    }
    assert(max_d < INF);
    return {max_d,idx};
}

int main(){
    int n;
    cin >>n;
    vector<int> u(n),v(n),l(n);
    rep(i,n){
        cin >>u[i] >>v[i] >>l[i];
        --u[i];
        --v[i];
        if(u[i]>v[i]) swap(u[i],v[i]);
        G[u[i]].pb({v[i], l[i]});
        G[v[i]].pb({u[i], l[i]});
    }

    par[0] = -1;
    dfs(0);

    int C = cycle.size();
    vector<ll> d(C+1),w(C);
    rep(i,C){
        // calc d
        queue<P> que;
        que.push({0,{cycle[i],-1}});
        while(!que.empty()){
            P now = que.front();
            que.pop();
            d[i] = max(d[i], now.fi);
            int vv = now.se.fi, pp = now.se.se;
            for(const auto &e:G[vv])if(!is_cycle[e.to] && e.to != pp){
                que.push({now.fi+e.cost, {e.to,vv}});
            }
        }

        // calc w
        for(const auto &e:G[cycle[i]]){
            if(e.to == cycle[(i+1)%C]) w[i] = e.cost;
        }
    }

    vector<ll> pred(C+1),sufd(C+1);
    vector<ll> pref(C+1),suff(C+1);

    ll dt = -INF;
    ll sw = 0;
    pred[0] = pref[0] = d[0];
    for(int i=1; i<C; ++i){
        dt = max(dt,d[i-1]) + w[i-1];
        pred[i] = max(pred[i-1], dt+d[i]);

        sw += w[i-1];
        pref[i] = max(pref[i-1], d[i]+sw);
    }

    sufd[C] = suff[C] = -INF;
    dt = -INF;
    sw = 0;
    for(int i=C-1; i>=0; --i){
        dt = max(dt,d[i+1]) + w[i];
        sufd[i] = max(sufd[i+1], dt+d[i]);

        sw += w[i];
        suff[i] = max(suff[i+1], d[i]+sw);
    }

    int idx = 0;
    ll min_inconvenience = INF;
    rep(i,C){
        ll t_inconv = max({pref[i]+suff[i+1], pred[i], sufd[i+1]});
        if(min_inconvenience > t_inconv){
            min_inconvenience = t_inconv;
            idx = i;
        }
    }

    int del = 0;
    int ru = cycle[idx], rv = cycle[(idx+1)%C];
    if(ru>rv) swap(ru,rv);
    rep(i,N) G[i].clear();
    rep(i,n){
        if(u[i]==ru && v[i]==rv){
            ++del;
            continue;
        }
        G[u[i]].pb({v[i], l[i]});
        G[v[i]].pb({u[i], l[i]});
    }
    assert(del==1);

    int xx = farthest(0,n).se;
    cout << farthest(xx,n).fi << endl;
    return 0;
}