問題 問題リンク：https://codeforces.com/contest/1473/problem/F 次を満たす集合 を'strange'とする。 'strange'である集合 に対し の最大値を求めよ。 解法 いわゆる、「燃やす埋める問題」に落とし込めるので最小カットで解くことができる。 正負のペナ…

問題 問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403 解法 頂点に重み付きの価値がついているグラフの最大独立集合を求める問題。 なので枝刈り探索によって解くことができる。具体的な枝刈り方法はwataさんのスライドのp.28以…

問題 頂点 辺の無向が与えられる。最初、 番目の頂点には 人の兵士がおり、各兵士は隣接する頂点に移動するかその場にとどまるかを行う。ただし、兵士が移動できる辺の本数は1本までとする。 すべての移動後、 番目の頂点にいる兵士の人数を となるようにで…

問題 ICPC Europe Northwestern Regional 2012 A V頂点E辺の有向グラフが与えられる。このグラフ上で始点から終点への2本のパスを作る。ただし、2つのパスは始点と終点以外で同じ頂点を共有しないようにする。このとき、パスに使用される辺のコストの総和を…

問題 ICPC Regionals 2011 Europe - Northeastern の問題 問題リンク：UVa Live Archive 5920 - Kingdom Roadmap N頂点の木が与えられる。どの1つの辺を取り除いても全体の連結性が保たれるように辺を追加するとき、必要な辺の最小本数とその追加する場所を…

問題 問題リンク：There is No Alternative N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。 解法 最小全域木に1つ辺を追加したとき、その辺によって作ら…

森に枝を挿すと木になる 問題概要 N頂点M辺の森が与えられます。頂点には0から N−1の番号がついています。辺(xi, yi)は頂点xiとyiをつなげています。 各頂点iには aiという値が定まっています。 あなたは与えられた森に辺を追加して連結にしたいです。 辺を…

問題概要 N頂点A辺からなる重み付き有向グラフがあり、各辺の重みは文字列で与えられます。始点から終点への文字列が辞書順で最小になるような経路を選んだときのその文字列を出力してください。ただし始点から終点への経路が存在しない、または無制限に辞書…

D - バスと避けられない運命 問題概要 N頂点M辺の連結な重み付き無向グラフが与えられます。各頂点との距離の最大値が最小となる頂点を選びその頂点との距離の最大値を出力してください。 制約 2 ≦ N ≦ 300 N-1 ≦ M ≦ 44850 1 ≦ ti ≦ 103 二重辺、自己ループ…

問題リンク https://onlinejudge.u-aizu.ac.jp/problems/2419 問題概要 H*Wのマス目上を上下左右に移動します。Sからスタートし全てのMを一回以上通りながらGにたどり着くのにかかる最短時間を求めてください。隣り合うマス目の移動には1秒かかりますが穴の…