2016-03-21から1日間の記事一覧
問題 codeforces.com 解法 さっきの問題とよく似ています。 mayokoex.hatenablog.comまず, 頂点 0 からつながる頂点を列挙します。これが k 個以下だったら impossible です。で, それらの点からスタートして, 0 以外の頂点となるべく連結させていきます。こ…
問題 xmascontest2015.contest.atcoder.jp 解法 S: (禁止されている辺の集合), unvisit: (現時点でまだ訪れていない頂点の集合) とします。で, ある頂点 v に訪れた時は, unvisit の頂点を見ていって, (u, v) が S に含まれるものでなかったら v -> u に辺を…
問題 codeforces.com 解法 もう問題から「最大流使って下さい」というにおいがプンプンします。答えを二分探索して, 各辺について「くまが何匹通れるか」というのを cap にします。この時, 頂点 0 から頂点 n-1 へのフローが x 以上であるならば, すべてのく…
問題 codeforces.com 解法 条件が合わない場所がたくさんありすぎると, どうスワップしても条件が合わない場所すべてに対応することが出来ないので, NG です。ということで, 条件が合わない場所が 10 箇所より多い場合は問答無用で 0 を出力しましょう(多分 …