最大流に帰着
最終的に最大流に帰着して解く問題の大部分が
まず最小カット問題に帰着する
負の辺を消して最大流問題にする
最大流ライブラリで解く
という流れだし、最小カット問題に帰着しようとしてる時にフローのことを考えるのは混乱の元なので最小カットに帰着に移動した。
ここには最小カットを使わないで最大流でとか問題があれば書く。
---
最大流に帰着
from 最小費用流に帰着
Related Pages
- →帰着する力×計算量の見積もり×abc165c×agc048×思考の部品×abc034c×arc106d×貪欲法の証明パターン×abc146d×agc038a×agc036a×arc083a×arc026b×arc040c×arc024b×cf17_final_c×agc024b×soundhound2018_summer_qual_c×panasonic2020_d×arc091b×公式より小オーダー×abc147d×abc006c×abc070d×abc125c×agc014b×agc018a×abc132d×abc014c×aising2019c×code_festival_2017_quala_c×abc109d×abc112c×AGC003B×arc062b×agc024c×indeednow_2015_quala_c×abc016d×abc121d×agc033a×arc054b×arc092a×arc052b×abc080c×tenka1_2017c×abc105c×abc032c×abc054c×diverta2019_2_c×indeednow_2015_qualc_c×abc089d×abc157d×abc012d×abc154e×arc032b×abc126d×arc081b×abc138e×tenka1_2018_c×nikkei2019_qual_c×abc019c×abc140d×arc042b×arc064a×arc034b×abc124d×arc037b×arc097b×arc097a×arc036b×abc096d×abc150d×doing×sumitb2019_e×nomura2020c×code_festival_qualb_c×m_solutions2019d×agc019b×abc103d×agc029b×arc087b×arc014c×abc165e×agc006b×codefestival_2016_final_c×agc031b×agc022b×agc032b→
- →2色で塗り分け→グラフのカット×グラフのカット×2色での塗り分け×最大カット→二部グラフなら片側を反転×最大カット×グリッドグラフ×二部グラフ×abc193×Project Selection Problem→
- →atcoderエントリーポイント×atcoder失敗リスト×二分探索チェックリスト×列に対して決まる値→列の区間でdp×最大化を二分探索で×実数に対する大小判定×値域と定義域の交換×最小カットに帰着×競技プログラミングで解法を思いつくための典型的な考え方×問題変換→
- →僕のatcoderの学び方(〜青)×past5o×atcoder失敗リスト×abc175e×abc174f×abc172e×abc178f×arc106c×arc106×arc105c×arc105d×arc104c×arc107d×貪欲法×最小カットに帰着→
- →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜PAST上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×AtCoderEntrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152_f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×educational_dp_contest×動的計画法×AtCoder Library Practice Contest×AtCoder Library×帰着する力×帰着訓練→
- →AtCoder Library×aclpc×aclpc_a×aclpc_b×aclpc_c×ACLPC D×aclpc_e×aclpc_f×aclpc_g×aclpc_h×aclpc_i×aclpc_j×aclpc_k×aclpc_l→
- →atcoder×AtCoder Library Practice Contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]