torus711 のアレ

主に競技プログラミングの問題について書きます

最小全域木

Codeforces #270, D : Design Tutorial: Inverse the Problem

問題文 http://codeforces.com/contest/472/problem/D 問題概要 の行列 が与えられる。 頂点からなる木であって、頂点 間の距離が となるものは存在するか? なお構成される木は、無向・重み付きであって、辺重みは全て正である。

TopCoder SRM 611, Division 1, Level 2 : Egalitarianism2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13008&rd=15844 問題概要 平面上に N 個の点がある。これらの点を頂点とし、二点間にそのユークリッド距離に等しい重みの辺を張ったグラフを考える。このグラフの全域木であって、辺重み…