10/24 PKU
2^10記念日
2375 Cow Ski Area
グリッド上の土地で、各マスごとに標高が決まっている。隣り合うマスの間なら、高いマスから低いマスへスキーで滑れる。同じ高さなら双方向へ滑れる。今、うまくリフトを建設し、任意のマスの間をリフトとスキーで移動できるようにしたい。リフトは何個必要か。
同じ高さをUnion-Findでまとめると、サイクルのない有向グラフができるので、「起点」「終点」を数え、最大値をとるだけ
2^10記念日
グリッド上の土地で、各マスごとに標高が決まっている。隣り合うマスの間なら、高いマスから低いマスへスキーで滑れる。同じ高さなら双方向へ滑れる。今、うまくリフトを建設し、任意のマスの間をリフトとスキーで移動できるようにしたい。リフトは何個必要か。
同じ高さをUnion-Findでまとめると、サイクルのない有向グラフができるので、「起点」「終点」を数え、最大値をとるだけ