让 Facebook 广告成为最大流量问题
Making Facebook ads a Maximum Flow Problem
问题
Facebook 拥有各种个人信息，因此可以通过承诺广告商投放针对特定人群的广告来吸引广告商。广告商正在流口水，准备花大笔钱。现在 Facebook 正试图找出一种有效的方法来向尽可能多的用户投放有针对性的广告。
此过程的第一步是将人们分类为人口统计群体。在 Facebook 上，这些分类可能基于诸如地理位置、年龄、对某种音乐的兴趣、大学专业等因素。我们假设此步骤由数据挖掘组负责，并且他们已经确定了 k 个人口统计组 G_1、G_2、...、G_k。请注意，这些组可以重叠； G_1可能是住在Bellingham的人，G_2可能是喜欢披萨的人，G_3可能是计算机科学专业的学生。
Facebook 的营销部门正在与 m 个不同的广告商签订合同，向网站用户展示一定数量的广告。与第 i 个广告商的合同如下所示：
对于人口统计组的子集，X_i = {G_1, G_2, ..., G_k}，广告客户 i将仅向属于 X_i
中至少一个人口统计群体的用户展示其广告
对于数字 r_i，广告客户每分钟至少向 r_i 用户展示其广告
现在考虑显示一分钟广告的问题。具体来说，您希望创建一种方法，在此时向每位用户展示不超过一个广告，以满足尽可能多的广告合同。假设在给定的时间内网站上有 n 个用户，我们知道用户 j 属于人口统计组的特定子集。
你能否将该问题表述为最大流量问题，并解释如何确定此时是否可以向每个用户展示一个广告，以便 Facebook 的广告与 m广告商满意吗？如果可能的话，你应该解释一下如何将用户与广告配对以满足合同。
注意：请给出图的结构（节点和边是什么），这些边的容量，以及在描述如何使其成为最大流问题时的源和汇。
我的困惑：
我真的很纠结从哪里开始解决这个问题。
可以肯定的是，源似乎应该是广告，出边指向每个人，容量为 1。（此时这是对每个用户的单个广告）
这似乎也可能存在一个双向匹配图结构，其中人们指向他们所在的类别。
但是，我很困惑有多个不同的顾问适合所有这些。
但是，我上面的所有想法都可能是错误的，我真的很纠结。
这可以通过最大流的概括来解决：最小成本流。我不相信这可以用香草最大流量解决，因为问题陈述中有这句话，
Specifically, you want to create a way to show no more than one ad to each user at this minute to satisfy as many of the advertising contracts as possible.
为了满足这一说法，在最大流量问题中，连接到广告商的每条边都需要最小容量（在某些文本 [1] 中仍然被认为是最大流量问题的一个小变体。）也就是说，即使它可以作为最大流量来解决，MCF 公式也是一种更自然、更简单的应用工具，因为您可以轻松地将它扩展到包括每个合约的（整数）值，从而使每分钟的利润最大化。
解决这个问题的MCF是一个简单的层图：
s -> A -> G -> U -> t
其中 s 是源，t 是汇，A 是广告商层，G 是人口统计层，U是用户层。 ->符号表示从上一层到下一层存在有向节点。除非另有说明，否则每条边的成本为 0，容量为 1.
放置来自 s -> A_i 的边，其容量为 r_i 和一些较大的负常数 M 作为成本。还要从 s -> A_i 添加一条成本为 0 且容量无限的边。这些边缘集确保我们通过奖励每个合约价值 -M > 0（成本 M < 0）来满足尽可能多的合约。请注意，对我们来说，一个自然的扩展是每个合同 M_i，这反映了它对 Facebook 的实际价值。
如果 A_i 对人口统计组感兴趣，请放置来自 A_i -> G_j 的边。将每条边的容量设置为无限，将 weight/cost 设置为 0.
如果用户 u_k 属于人口统计组 G_j，则放置来自 G_j -> u_k 的边。将容量设置为 1，将成本设置为 0。
从 u_k -> t 中放置容量为 1 且成本为 0 的边，以确保每个用户只看到一个广告。
使用任何最小成本流算法解决此网络流问题，并使用流直接告诉您在给定约束的情况下可以满足多少合约。
[1] https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/25-maxflowext.pdf
问题
Facebook 拥有各种个人信息，因此可以通过承诺广告商投放针对特定人群的广告来吸引广告商。广告商正在流口水，准备花大笔钱。现在 Facebook 正试图找出一种有效的方法来向尽可能多的用户投放有针对性的广告。
此过程的第一步是将人们分类为人口统计群体。在 Facebook 上，这些分类可能基于诸如地理位置、年龄、对某种音乐的兴趣、大学专业等因素。我们假设此步骤由数据挖掘组负责，并且他们已经确定了 k 个人口统计组 G_1、G_2、...、G_k。请注意，这些组可以重叠； G_1可能是住在Bellingham的人，G_2可能是喜欢披萨的人，G_3可能是计算机科学专业的学生。
Facebook 的营销部门正在与 m 个不同的广告商签订合同，向网站用户展示一定数量的广告。与第 i 个广告商的合同如下所示：
对于人口统计组的子集，X_i = {G_1, G_2, ..., G_k}，广告客户 i将仅向属于 X_i
中至少一个人口统计群体的用户展示其广告对于数字 r_i，广告客户每分钟至少向 r_i 用户展示其广告
现在考虑显示一分钟广告的问题。具体来说，您希望创建一种方法，在此时向每位用户展示不超过一个广告，以满足尽可能多的广告合同。假设在给定的时间内网站上有 n 个用户，我们知道用户 j 属于人口统计组的特定子集。
你能否将该问题表述为最大流量问题，并解释如何确定此时是否可以向每个用户展示一个广告，以便 Facebook 的广告与 m广告商满意吗？如果可能的话，你应该解释一下如何将用户与广告配对以满足合同。
注意：请给出图的结构（节点和边是什么），这些边的容量，以及在描述如何使其成为最大流问题时的源和汇。
我的困惑： 我真的很纠结从哪里开始解决这个问题。
可以肯定的是，源似乎应该是广告，出边指向每个人，容量为 1。（此时这是对每个用户的单个广告）
这似乎也可能存在一个双向匹配图结构，其中人们指向他们所在的类别。
但是，我很困惑有多个不同的顾问适合所有这些。
但是，我上面的所有想法都可能是错误的，我真的很纠结。
这可以通过最大流的概括来解决：最小成本流。我不相信这可以用香草最大流量解决，因为问题陈述中有这句话，
Specifically, you want to create a way to show no more than one ad to each user at this minute to satisfy as many of the advertising contracts as possible.
为了满足这一说法，在最大流量问题中，连接到广告商的每条边都需要最小容量（在某些文本 [1] 中仍然被认为是最大流量问题的一个小变体。）也就是说，即使它可以作为最大流量来解决，MCF 公式也是一种更自然、更简单的应用工具，因为您可以轻松地将它扩展到包括每个合约的（整数）值，从而使每分钟的利润最大化。
解决这个问题的MCF是一个简单的层图：
s -> A -> G -> U -> t
其中 s 是源，t 是汇，A 是广告商层，G 是人口统计层，U是用户层。 ->符号表示从上一层到下一层存在有向节点。除非另有说明，否则每条边的成本为 0，容量为 1.
放置来自 s -> A_i 的边，其容量为 r_i 和一些较大的负常数 M 作为成本。还要从 s -> A_i 添加一条成本为 0 且容量无限的边。这些边缘集确保我们通过奖励每个合约价值 -M > 0（成本 M < 0）来满足尽可能多的合约。请注意，对我们来说，一个自然的扩展是每个合同 M_i，这反映了它对 Facebook 的实际价值。
如果 A_i 对人口统计组感兴趣，请放置来自 A_i -> G_j 的边。将每条边的容量设置为无限，将 weight/cost 设置为 0.
如果用户 u_k 属于人口统计组 G_j，则放置来自 G_j -> u_k 的边。将容量设置为 1，将成本设置为 0。
从 u_k -> t 中放置容量为 1 且成本为 0 的边，以确保每个用户只看到一个广告。
使用任何最小成本流算法解决此网络流问题，并使用流直接告诉您在给定约束的情况下可以满足多少合约。
[1] https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/25-maxflowext.pdf