https://atcoder.jp/contests/past202104-open/tasks/past202104_o
前提知識
解説
https://atcoder.jp/contests/past202104-open/submissions/22667026
最終問題。今までなかなか見たことがない難しい問題。
M≦N+10という見慣れない条件があるので、これをうまく使うんだろうということは分かるのだが、そこから一歩飛躍するのが難しい。
順番に考えていこう。
より簡単な問題をまずは考えてみる
よくある問題として、M=N-1の場合、グラフが木であった場合をまずは考えてみよう。
木上での最短経路問題はよくあるテーマであるので、調べると色々出てくると思うので、調べて学習してきてほしい。
正直この部分ができていないとこれ以降は難しい。
累積和とLCAがあればこの問題は解決できる。
自分はLCA部分をHL分解で解決していて、累積和も組み込んだやつをライブラリとして実装しているので使うだけだった。
この辺は良く要求される部分なので、ライブラリ化しておくのもいいだろう。
今回の問題ではどうしようか
ここまでで木上の二頂点間については最短距離が求められるようになった。
だが、今回の問題は木ではない。
しかし、一部の辺を除けは木の状態となっており、最大11本辺を刈れば木にできる。
これをdfsを使って、これをやろう。
無向グラフに対してdfsを行っていく。
木っぽくdfsを行っていくが、既に訪問済みの頂点へ向かう辺については使用せずに別途メモっておく。
これは後退辺とも呼ばれ、この辺を除けば木として成立する。
これで最短経路を求めてしまえば、今回の問題で木として作った無向グラフだけを通る最短経路は高速に求められるようになった。
後退辺を使った最短経路
後退辺を含むような最短経路も効率良く求めてやりたい。
後退辺は最大11本なので、その端点である頂点も22個となる。
これはかなり少ない数であるので、この頂点間での最短経路を求めることは難しくない。
具体的には、後退辺の端点で使われている頂点だけを頂点として、その間に以下のルールで辺を張る
- D[a][b] = 頂点aから頂点bへの木上での最短経路
- D[a][b] = 頂点abを端点として持つ後退辺があるときに1
頂点数は最大22なので、ワーシャルフロイドでサクッと計算してしまえる。
頂点も1,2,3にマッピングするのも面倒なので、mapでやってしまえば問題ない。
後は、後退辺を使った最短経路を組み込むために、この後退辺の端点を全探索して、
u -> 後退辺の端点の1つの頂点a -> 後退辺の端点の1つの頂点b -> v
というルートを全探索する。
これはdistance(u, a) + D[a][b] + distance(b, v)として書ける。
これの最小値も答えとして考えれば、最適解が導ける。
/* int d[V][V]; REP(i, V) REP(j, V) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } // ここで辺のコストを指定 rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) chmin(D[i][j], D[i][k] + D[k][j]); */ int N, M; vector<int> E[101010]; int Q; HLDecomposition hld; map<int, map<int, int>> D; //--------------------------------------------------------------------------------------------------- vector<pair<int, int>> unused; bool vis[101010]; void dfs(int cu, int pa = -1) { vis[cu] = true; fore(to, E[cu]) if (to != pa) { if (vis[to]) { unused.push_back({ cu, to }); continue; } hld.add(cu, to); dfs(to, cu); } } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, M) { int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } hld.init(N); dfs(0); hld.build(0); vector<int> targets; fore(p, unused) { targets.push_back(p.first); targets.push_back(p.second); } sort(all(targets)); targets.erase(unique(all(targets)), targets.end()); fore(x, targets) fore(y, targets) D[x][y] = hld.distance(x, y); fore(p, unused) D[p.first][p.second] = D[p.second][p.first] = 1; fore(k, targets) fore(i, targets) fore(j, targets) chmin(D[i][j], D[i][k] + D[k][j]); cin >> Q; rep(i, 0, Q) { int u, v; cin >> u >> v; u--; v--; int ans = hld.distance(u, v); fore(x, targets) fore(y, targets) chmin(ans, hld.distance(u, x) + D[x][y] + hld.distance(y, v)); printf("%d\n", ans); } }
