https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0435

前提知識

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0435/review/5811215/hamayanhamayan/C++14

まずは問題の整理をしていく。
与えられている地点と道路はグラフとしてマッピングすることができる。
この条件で面白い部分がある。

「どのように道路をたどっていっても、同じ地点に戻ることはない。」

これはグラフにループ構造が無いことを示している。
よって、このグラフはDAGであることがこの条件から分かる。
DAGはループの無い有向グラフのことであるのだが、DAGであることの有用性の1つとしてDPが行えるということがある。

この問題の前に

DAG上での問題という前提で考えると何回も似たような問題を見てきた。
トポロジカルソートをした上で、その順番でDP更新をしていく。
今回は2種類のDPを作っていくのだが、ちょっと別の問題を使って理解を深めていくことにしよう。

「始点から各地点に行くまでに何通りの移動方法があるか」という問題を考えてみる

「始点から各地点に行くまでに何通りの移動方法があるか」

これはDPで計算が可能である。

dp[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか

そのまんまなDPテーブルであるが、これを計算していけばいい。
トポロジカルソートをして、ソート順にDPを更新していく。
最初はdp[0] = 1として、更新時は地点cuから地点toへ移動可能だとするとdp[to] += dp[cu]とすればいい。

まず、これが理解できる所まで来ないと、この問題を理解することは難しい。
DPをしっかり理解していることと、トポロジカルソートをしっかり理解していることが必要なので、
そちらを学習してくるのもいいかもしれない。

では、これは理解できているものとして、もう少し進んだ問題を考える。

「始点から各地点に行くまでの全ての経路の長さの和は」

以下のように2つのdpを使って計算していこう。

comb[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか
tot[cu] ;= 始点から地点cuに行くまでの全ての経路の長さの和

tot[cu], comb[cu]がすでに計算されているものと仮定して、tot[to], comb[to]をどう計算するか考えよう。
combについては先ほどと同じなので、comb[to] += comb[cu]でよい。
問題はtotであるが、これまでの経路の長さの和は考慮されるべきなので、tot[to] += tot[cu]は決まっている。
これで考慮されていない長さはcuからtoに移る長さの分となる。
長さは1で固定で、本数は丁度comb[cu]と一緒になっている（！）
なので、考慮されていない長さの分も足してtot[to] += tot[cu] + comb[cu]で更新ができる。
初期状態はtot[cu] = 0, comb[cu] = 1で始まる。

元の問題

さて、やっと元の問題に戻れる。
今回求めたい問題は「始点→地点i→終点」となる全ての経路の長さの和を求める問題である。
これを分割して求めることにする。
始点からの経路と終点への経路に分けて計算する。

始点→地点iに至る全ての経路の長さの和を求めるには、1つ前にやった問題をやれば求めることができそうである。
仮に地点i→終点の移動方法が1通りである場合は、1つ前にやった問題の結果をそのまま使用すればいいのだが、
複数ある場合は、その組み合わせ分だけ、その経路の長さの和が使われることになる。
なので、地点i→終点の移動方法も計算したくなる。

始点→地点iの計算は先ほどやったが、同じ問題を地点i→終点で計算するにはすべての辺の方向を逆転させて
同じ計算をすればいい。
辺の方向を逆転させることで経路が変化することはないので、これで問題ない。

答えのアルゴリズム

長々書いてしまった。答えを簡潔にここから書き始める。

始点→地点iについて、comb, totを計算する。これをcomb1, tot1としておく。
次に辺の方向を逆転させて、同じ計算をして、
地点i→終点について、comb, totを計算する。これをcomb2, tot2としておく。

各地点iについて、
始点→地点iの全ての経路の長さの和はcomb1[i] * tot2[i]で計算ができ、
地点i→終点の全ての経路の長さの和はcomb2[i] * tot1[i]で計算ができるので、
「始点→地点i→終点」となる全ての経路の長さの和はcomb1[i] * tot2[i] + comb2[i] * tot1[i]となる。

int N, M;
int u[2510], v[2510];
//---------------------------------------------------------------------------------------------------
pair<vector<ll>, vector<ll>> getCombination(int root) {
    vector<int> E[50];
    TopologicalSort ts(N);
    vector<int> ord;

    rep(i, 0, M) {
        E[u[i]].push_back(v[i]);
        ts.add_edge(u[i], v[i]);
    }
    ts.sort(ord);

    vector<ll> comb(N, 0), tot(N, 0);
    comb[root] = 1;
    tot[root] = 0;
    fore(cu, ord) fore(to, E[cu]) {
        comb[to] += comb[cu];
        tot[to] += tot[cu] + comb[cu];
    }
    return { comb, tot };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> u[i] >> v[i], u[i]--, v[i]--;

    auto p1 = getCombination(0);
    rep(i, 0, M) swap(u[i], v[i]);
    auto p2 = getCombination(N - 1);

    rep(i, 0, N) {
        ll ans = p1.first[i] * p2.second[i] + p2.first[i] * p1.second[i];
        cout << ans << endl;
    }
}

はまやんはまやんはまやん

hamayanhamayan's blog

高速道路網 [パソコン甲子園2020 予選 H]