最大フロー
問題 問題概要 頂点の間の容量が与えられる. 複数のスタートから一つのゴールまで最大どのくらいのものを運ぶことができるか. 解法 G個のスタート地点があるので, スタート地点の頂点を新たに作り, そこから魔導石に近い魔法使いへ辺の容量がINFの辺をはる. …
問題 問題概要 Aliceから順に相手の欠点を選ぶ。次にボブは選ばれた欠点と関係あるAliceの欠点を選ぶ。これを続けていき、選べなくなったら負け。 解法 2部マッチングかなて感じはするが、どちらが勝つのかという判定をどうすればいいかわからなかった。 感…
問題 問題概要 青と赤のカードがある。青と赤のカードを選び、その2つの数が1より大きい約数を持つなら取ることができる。一度取った数字は次から選ぶことができない。何組のカードが取れるか。 解法 ペアの個数はペアを作る組によって変わってくる。約数を…
問題 問題概要 省略 解法 2部マッチングでできるのか、て感じ。公式解説を見ればわかる。実装はs,tを追加して、最大フローを求める感じで書いたもの。 ミス 制約が小さければ、bitDPでもできるぽい。グラフ問題に落とせるようにしたい。 コード #include <iostream> #i</iostream>…
問題 問題概要 省略 解法 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>…
問題 問題概要 省略 解法 最大フロー確認問題。 ミス 蟻本のやつを写経したけど、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>…
問題 問題概要 最大フロー. 解法 sから作画に与えられたjで辺を貼り、作画から条件を満たす監督に、辺の流量無限大で流し、監督からtへ与えられた、cで辺を貼る.このグラフを使って、 最大フローを求めればいい. ミス なし. コード #include <iostream> #include <algorithm> #inc</algorithm></iostream>…