2017-02-09

CF 701 F - Break Up

問題

問題概要

$n$ 頂点 $m$ 辺の無向グラフがある。グラフが連結である保証はない。

いま、ある辺を削除して頂点 $s$ から頂点 $t$ への移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストがついている( $w_i$ とする)ので、削除のコストが最小になるように削除した時の、そのコストと、その時に削除する辺はどれになるかを答えよ。ただし、不可能な場合には-1とだけ答えよ。

$2 \le n \le 1000$
$0 \le m \le 30000$
$1 \le w_i \le 10^9$

アイデア

まず、もとのグラフで $s$ と $t$ がもともと繋がっていなければ答えは0になる。以下、つながっている場合を考える。

もし、1つの辺の削除によって $s$ と $t$ を連結でなくすることが可能なら、その辺は $s$ から $t$ へのあらゆるパスに含まれることになる。よって、二重辺連結成分分解によって橋をみつけて、 $s$ から $t$ へのある1つのパス上を眺めてそのパス上にある橋のコストをみていけば良い。

2つの辺を削除して $s$ と $t$ の連結を切ることを考えるとき、削除する辺のうちの1つは見つかった1つのパス上になければならない(でないとそのパスを使うことが出来るから)。パス上のある辺 $e$ を削除したと考えると、この1つの辺を削除したグラフに対して橋を見つけて、あるパス上の橋を削除すべきということになる。

このいずれでも不可能な時は-1と答えることになる。

実装(C++)

2017-02-08

CF 701 E - Connecting Universities

Codeforces programming

問題

Problem - E - Codeforces

問題概要

頂点数 $n$ の木があり、頂点には $1$ から $n$ の番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、 $2k$ 個の頂点番号が指定される。それらを $u_1 , u_2 , \cdots , u_{2k}$ とする。これら $2k$ 個の頂点から、 $k$ 個のペアを作る。そのペアの木における距離の総和を最大化するようにペアを作った時、その総和の値を求めよ。

$2 \le n \le 200000$
$1 \le k \le n/2$
$1 \le u_i \le n$

アイデア

頂点 $1$ を根として考える。すると、DFSによって次の値を各頂点に対して求めることが出来る：

$s_i$ : 頂点iを根とした部分木以下にある指定されている頂点の個数(自分も含む)

最適なペアを取ることの出来る状況を考えてみる。

そこで、頂点 $v$ とその親の間にある辺を考えてみると、その辺は $min(s_v , 2k - s_v)$ 個のペアのパス上にあることになると言える。これはなぜかというと、まず、これ以上のペアのパス上になることは、この辺を挟んだ位置にあるそれぞれの頂点の個数を考えてみると、物理的に有り得ない。逆にこれ未満である状況を考えると、 $v$ を根とする部分木の中にある頂点同士 $a$ と $b$ がペアになっており、その部分木には含まれない頂点同士 $c$ と $d$ がペアになっているということになる。そして、木の性質上、このペアを $a$ と $c$ 、 $b$ と $d$ に変えることで $a$ から $b$ へのパス上の辺と $c$ から $d$ へのパス上の辺を全てカバーでき、かつパスを長くすることが出来る組み合わせなのでこのような組み合わせは最適ではないことが分かり、上記のことは正しいということが分かった。