srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

最大フロー

九州大学プログラミングコンテスト2014 H - お風呂は気持ちいい

問題 問題概要 頂点の間の容量が与えられる. 複数のスタートから一つのゴールまで最大どのくらいのものを運ぶことができるか. 解法 G個のスタート地点があるので, スタート地点の頂点を新たに作り, そこから魔導石に近い魔法使いへ辺の容量がINFの辺をはる. …

aoj 2480 - Blame Game

問題 問題概要 Aliceから順に相手の欠点を選ぶ。次にボブは選ばれた欠点と関係あるAliceの欠点を選ぶ。これを続けていき、選べなくなったら負け。 解法 2部マッチングかなて感じはするが、どちらが勝つのかという判定をどうすればいいかわからなかった。 感…

aoj 1163 - Cards

問題 問題概要 青と赤のカードがある。青と赤のカードを選び、その2つの数が1より大きい約数を持つなら取ることができる。一度取った数字は次から選ぶことができない。何組のカードが取れるか。 解法 ペアの個数はペアを作る組によって変わってくる。約数を…

yukicoder No.421 しろくろチョコレート

問題 問題概要 省略 解法 2部マッチングでできるのか、て感じ。公式解説を見ればわかる。実装はs,tを追加して、最大フローを求める感じで書いたもの。 ミス 制約が小さければ、bitDPでもできるぽい。グラフ問題に落とせるようにしたい。 コード #include <iostream> #i</iostream>…

aoj GRL_7 A Matching - Bipartite Matching

問題 問題概要 省略 解法 2部マッチングの確認問題 ミス 蟻本のやつを写経した。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; co</algorithm></cstring></vector></cstdio></iostream>…

aoj GRL_6 A Network Flow - Maximum Flow

問題 問題概要 省略 解法 最大フロー確認問題。 ミス 蟻本のやつを写経したけど、c++11だと通らないなー。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++)</algorithm></cstring></vector></cstdio></iostream>…

yukicoder No.177 制作進行の宮森あおいです!

問題 問題概要 最大フロー. 解法 sから作画に与えられたjで辺を貼り、作画から条件を満たす監督に、辺の流量無限大で流し、監督からtへ与えられた、cで辺を貼る.このグラフを使って、 最大フローを求めればいい. ミス なし. コード #include <iostream> #include <algorithm> #inc</algorithm></iostream>…