![Step 2
● 各辺が最長パスに含まれうるかどうか判定する。
● vのsourceからの最長距離をd[s→v]とする。
● vのsinkまでの最長距離をd[v→t]とする。
● これらは簡単なDPで計算可能。
● 辺(u,v)が最長パスに含まれうる
? DAGの最長パス=d[s→u] + 1 + d[v→t]](https://image.slidesharecdn.com/trip-130313022155-phpapp01/85/Trip-7-320.jpg)
![Step 2
● DAGの最長パスに含まれうる辺(u, v)をd[s→u]
の値で部分集合に分類する。
● このとき、サイズ1の部分集合に含まれる辺が答と
なっている。](https://image.slidesharecdn.com/trip-130313022155-phpapp01/85/Trip-8-320.jpg)
Trip
- 1. 社員旅行 原案：komiya 解答：fura2, komiya スライド：komiya
- 2. 問題概要 ● DAGが与えられる。 ● X:=min{k|頂点集合をk個の部分集合に分け、ど の部分集合の2点を選んでもパスが存在しない} ● どれか1本辺を選んで取り除き、Xが小さくなるよ うにしたい。どの辺を選べばよいか全て求めよ。 ● 頂点数≦10^5 ● 辺数≦2*10^5
- 3. Step 1 ● Xはどうやって求めればよい？ ● 頂点集合で、どの2点を選んでもパスが存在しな いようなものをantichainと呼ぶことにする。 ● 頂点集合で、うまく順番を入れ替えて1列に並び 替えると隣接する2点間に必ずパスが存在するよ うなものをchainと呼ぶことにする。 ● X=「頂点集合を最小いくつのantichainに分割で きるか」
- 4. Step 1 ● XはDAGのchainの最大サイズと等しい。 ● (証明): X ≧ max(|chain|)は明らか。 X ≦ max(|chain|)は、各頂点をsource(入次数0 の頂点)からの最長距離で分類すればantichain への分割となっていることから示される。 ● sourceからの最長距離の代わりに、sink(出次数 0の頂点)までの最長距離で分類しても同じ。
- 5. Mirskyの定理 ● 実はこれはMirskyの定理と呼ばれている。 ● DAGで次が成り立つ。 chainの最大サイズ = antichainへの最小分割数 ● Dilworthの定理の双対となっているらしい。 ● Dilworthの定理 DAGで次が成り立つ。 antichainの最大サイズ = chainへの最小分割数
- 6. Step 2 ● 元の問題は次の問題へと帰着される。 「取り除いたときDAGの最長パスが真に短くなる ような辺を全て求めよ。」 ● さらに次のように言い換えられる。 「DAGの最長パスに必ず含まれる辺を全て求め よ。」
- 7. Step 2 ● 各辺が最長パスに含まれうるかどうか判定する。 ● vのsourceからの最長距離をd[s→v]とする。 ● vのsinkまでの最長距離をd[v→t]とする。 ● これらは簡単なDPで計算可能。 ● 辺(u,v)が最長パスに含まれうる ? DAGの最長パス=d[s→u] + 1 + d[v→t]
- 8. Step 2 ● DAGの最長パスに含まれうる辺(u, v)をd[s→u] の値で部分集合に分類する。 ● このとき、サイズ1の部分集合に含まれる辺が答と なっている。
- 9. 補足 ● DAGの自明なトポロジカル順序が与えられている ので、再帰やスタックを使って書く必要はない。