二分图 - 卖家和买家 [英] bipartite graph--Sellers and Buyers

问题描述

给几个卖家和买家，每个卖家都有一定数量的产品，每个买家都想从卖家那里买几种产品。有些卖家不能与一些买家进行交易，如果买家无法获得足够的产品，交易就不会成功。如果我们知道有一种策略可以满足所有的买家，那么如何找到这种策略呢？

我画了一张图来说明问题，这只是一个例子。该问题希望您为每个买方提供交易策略，以便所有买方都能获得他们想要的足够多的产品。
卖家买家示例

解决方案

我假设一个买家可能从一个卖家购买多件东西。将它改为一个项目并不难。

这可以通过最大流算法来解决。直接从买方到其连接的卖方。为这些边分配容量b_i。 B_i是买方需要的金额。添加两个节点S，T。从S向所有买家添加边缘。将容量b_i分配给每个边。 B_i又是我需要的买家的金额。将每个卖方顶点的边添加到T.将容量S_i分配给这些边。 S_i是卖方的金额。找到从S到T的最大流量。如果它等于所有买家所需金额的总和，那么就有问题的解决方案，并且可以通过从买方到卖方的每个边缘的流量来找到（这是积分流定理的后续）。

Given several sellers and buyers, each seller has an amount of products, each buyer wants to buy several products from sellers. Some sellers can not transact with some buyers, if a buyer can not get enough products as he wants, the transaction will not succeed. If we know there is one strategy that can satisfy all buyers, how to find this strategy?

I draw a graph to illustrate the problem, this is just an example. The question wants you to provide a transaction strategy for each buyer so that all buyers can get enough products they want. seller buyer example

解决方案

I assume one buyer may buy multiple things from one seller. It is not hard to change it to one item.

This can be solved by maximum flow algorithm. Direct edges from buyer to their connected sellers. Assign capacity b_i for those edges. B_i is the amount the buyer needs. Add two nodes S,T. Add edges from S to all buyers. Assign capacity b_i to each of those edges. B_i is again the amount the buyer i needs. Add edges from every seller vertex to T. Assign capacity S_i to those edges. S_i is the amount the seller i has. Find the maximum flow from S to T. If it is equal to the sum of all buyers required amounts then there is a solution to the problem and it can be found by the amount of flow which goes through every edge from buyers to sellers (this is a follow up of integral flow theorem).

这篇关于二分图 - 卖家和买家的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！