10/24 PKU

2^10記念日

2375 Cow Ski Area

グリッド上の土地で、各マスごとに標高が決まっている。隣り合うマスの間なら、高いマスから低いマスへスキーで滑れる。同じ高さなら双方向へ滑れる。今、うまくリフトを建設し、任意のマスの間をリフトとスキーで移動できるようにしたい。リフトは何個必要か。

同じ高さをUnion-Findでまとめると、サイクルのない有向グラフができるので、「起点」「終点」を数え、最大値をとるだけ

1849 Two

木構造になっている道路を除雪したい。除雪車は2つある。各道路ごとに通るのに必要な燃料が決まっている。起点は決まっているがどこで終了してもかまわない。必要な燃料の量の最小値を求めよ。

ちょっと考えると(道路のコストの総和*2 - 直径)で解けることがわかる。起点は無視。