https://codeforces.com/contest/1633/problem/E 問題 N頂点M辺の連結無向グラフが与えられ、各辺にはwiの重みがある。 f(x) := sigma(wi - x)が最小になるように取った全域木のコスト とした時に、10^7個のxが与えられる。 全てのxについてf(x)を計算し、そ…

C: Gr-idian MST - CODE FESTIVAL 2016 qual B | AtCoder 問題概略 (H+1)*(W+1)個の頂点がある。 隣り合う縦に辺を貼るのに必要なコストはxの大きさにかかわらずpi 横も同様にqiかかる。 最小で全域機を作れ制約 H,W p,q解法 線を引いて考えてみると、辺の本…

D - Built? 問題概略 N個の街があり、座標(x,y)が与えられる 座標 (a,b)(a,b) にある街と座標 (c,d)(c,d) にある街の間に道を造るのには、min(|a−c|,|b−d|)min(|a−c|,|b−d|) 円かかります、最小全域木 制約 2≦N≦1052≦N≦105 0≦xi,yi≦1090≦xi,yi≦109 入力は全…