Graph

POJ 2914: Minimum Cut

http://poj.org/problem?id=2914これもフローとはまた違った話。全域最小カット。Stoer–Wagnerを使う。Stoer–Wagnerは 「点の集合からの辺のコストの合計が大きいもの点から取っていって、最後から二番目に取った点sと最後に取った点tの最小カットは tから生…

POJ 3713: Transferring Sylla

Mengerの定理より全域最小点カットを求めれば良い。すべての点対に対してフローを流せばできるが、それではTLE。 全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。全域最小点カットが2以上にな…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

Codeforces Round #423B: High Load

http://codeforces.com/contest/827/problem/B最初にrootを一つ決めて、あとはkコずつrootからまんべんなくつけていけば、木の高さが最小、かつその時の一番rootから離れているedgeの個数も最小になるのでこれが求めるグラフとなる。 int N, K; void solve()…

AtCoder Grand Contest 016E: Poor Turkeys

単調減少してから単調増加するPathがキーになることは分かったけど…ループがどうなるかよくわからなくなった。http://agc016.contest.atcoder.jp/tasks/agc016_eまずある一つの頂点xに注目する。操作を後ろから見て、i番目の人の操作が終わった際、何が生き…

AGC_016D: XOR Replace

http://agc016.contest.atcoder.jp/tasks/agc016_d うーん。Union Find見えてからが遅かった。EFもようわからん連結成分を考えれば良くて、変更前の数列のxorの値と変更後の数列のxorの値が等しいか異なるかで場合分け。 答えは(連結成分の数)+(異なる値の数…