典型タグ

最小費用流・circulation

流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。

この典型を扱う単元: 最小費用流・circulation

検索別名: min-cost flow、minimum-cost circulation、最小費用流

未知問からこの典型を見つける手掛かり

扱う対象
  • costed edge
  • flow
  • residual network
使う手掛かり
  • 利益最大化
  • 割当費用
  • 流量別
保つ不変量
  • potential
  • reduced cost
  • residual cycle
求めるもの
  • slope
  • 最大利益
  • 最小費用
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

関連する典型

  • 最大流・最小カット: 容量と保存則を持つflow模型へ辺費用と流量別最適化を加え、reduced costや残余cycleまで管理する拡張である。
  • 最短路モデル: potentialで非負化した残余graph上の最短路を、増加路選択の実装基盤にする。

学習成果と学習単位

  • 流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    最小費用流・circulationで学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。