AOJ-ICPC 2016.10.7
問題を解くのをさぼると死ぬ
問題
Reverse a Road II | Aizu Online Judge
問題概要
各辺の容量がの有向グラフが与えられる。
辺を一本だけ反転させ、 間の最大流を増加させられるか。
可能な場合はそのような辺は何本あるか。
解法
まず最大流を流し、残余グラフを作る。
残余グラフで から行ける頂点集合を
、
に行ける頂点集合を
とすると、
から
への辺が条件を満たす辺である。
問題
Vector Compression | Aizu Online Judge
問題概要
ベクトルの集合が与えられるので、任意の順番でベクトルを選んでいく。
あるベクトルを選ぶとき、既に選んだベクトルの1つを使ってベクトルを圧縮できる。
ベクトルを
で圧縮すると、
となる。(
は任意の実数)
全てのベクトルを選んだとき、それぞれのベクトルの大きさの和を最小化せよ。
解法
あるベクトルで別のベクトルを圧縮した時の大きさはを三分探索すれば求まる。(いい感じの式で計算することもできそう)
各ベクトルを頂点とし、ベクトルを使ってベクトル
を圧縮したときのベクトル
の大きさを辺
の重みとするような有向完全グラフを考える。
答えはそのグラフの最小有向全域木になる。
任意の頂点を根とすることができるので、あらかじめゼロベクトルをベクトルの集合に追加しておいて、それを根とする最小有向全域木を求めるとよい。
最小有向全域木はChu-Liuのアルゴリズムで求めることができる。
