CF 835 F - Roads in the Kingdom
問題
問題概要
頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。
このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。
このグラフから連結性を保ちつつ1つだけ辺を取り除く時の取り除いた後のグラフにおけるincovenienceの最小値を求めよ。
- 多重辺、自己ループは存在しない
- 1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される
アイデア
入力の条件から、「1つの辺を除いても、全体の連結性が保たれるような辺が存在することが保証される」ということは、取り除いた後のグラフは頂点辺で、全体が連結ということになるので、これは木である。つまり、与えられるグラフは木に1本だけ余計な辺を足した形になっていることが分かる。
そして、そのようなグラフではループが1つだけ存在し、それに木をいくつかくっつけたような形になっているとみることができ、今回の問題で取り除く対象にできるのはこのループ内の辺に限られることになる。あとは、このループ内の辺に対して削除対象を動かしながらその時のinconvenienceを高速に計算したい。
また、inconvenienceを考える時に、我々が最小化出来るものは「ループ内の辺を通る」パスについてしか出来ないので、それの最小化を考えることにする(例えば、ループ外に巨大な木がくっついていたら、その木の中同士の頂点が最大をとるペアになりそうだが、これはどうしようもないので考えない)。この最小化を考えて、取り除く辺を決定したら、取り除かれたグラフ上で木の直径を求めれば良い。
以下、考えやすいようにループの大きさをとして、頂点に通し番号をふってあるものとして考える。ループだけを考えれば良いようにするためにループ内の頂点に次のようなパラメータを持たせる:
- : 頂点に対してくっついている木の中の最も遠い頂点との距離
また、次のような値を計算しておく:
- : 頂点との間の辺の重み
- : 頂点の間で最も離れたペアの距離
- : 頂点の間で最も離れたペアの距離
- : 頂点の間で、頂点と最も離れた頂点の距離
- : 頂点の間で、頂点と最も離れた頂点の距離
これらを事前に計算しておくと、頂点との間の辺を切った場合のinconvenienceはで表せるので、全体でで求められる。
実装(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; }