algorithm - 最大フローを使用してこれを解決するにはどうすればよいですか?

Question

C1 都市はいくつかの商品を喜んで販売し、他の C2 都市はいくつかの商品を喜んで購入します (各都市は商品を販売または購入できますが、両方を行うことはできません)。各販売都市はその商品を 1 つの都市にのみ販売し、各購入都市は 1 つの都市からのみ商品を購入します。

あなたの目標は、交換される商品の量が最大になるように利己的な都市を接続することです。

難しいのは、各都市が 1 つの都市に対してのみ商品を売買できるという制限です。

Answer 1

最小コスト最大フローを使用してこの問題を解決する必要があります。フロー 1 の 2 つの都市それぞれの間にエッジを追加し、この都市のペアの売買額の最小値を否定します。たとえば、都市 A がセル X ユニットを喜んで売却し、都市 B が Y ユニットを喜んで購入する場合Z = min(X, Y)、フロー 1 とコスト で A と B の間のエッジを計算して追加します-Z。