需要简单的图形解决问题的建议
我的一位同事向我提出了一个在线评委网站上的练习，这基本上是一个关于小城镇疏散计划的图解问题。
我不需要答案(我也不想要它)，我只需要一个建议，关于哪种方法是解决它的最好方法，因为我对这类问题还是个新手。
问题包括有工人的城镇建筑和核弹掩体，以防发生核攻击。我必须构建一个算法，将每栋建筑的工人分配到一个或多个放射性物质避难所，但在某种程度上，一些避难所不会变得过于拥挤，而另一些避难所几乎是空的(否则我只会让工人去最近的一个)。
问题是：http://acm.timus.ru/problem.aspx?space=1&num=1237
到目前为止，我所做的是为每一栋建筑获得最近的避难所，并从该建筑中转移与避难所容量相等的工人数量。然后搬到下一栋楼去。但有时工人的数量大于避难所的容量，在这种情况下，在我迭代每一座建筑后，我会再次迭代，然后应用相同的算法，直到每一座建筑都有0名工人，问题是这几乎不是解决问题的最佳方法。
任何提示都是受欢迎的，请不要觉得我在询问答案，我只是想要一个正确方向的建议来解决它。
提前谢谢。
回答 2
Stack Overflow用户
发布于 2010-05-19 16:42:57
这看起来与Transhipment Problem完全一样，可以(显然)使用线性规划来解决。(我说很明显，因为这看起来像是整数线性规划的一个实例)。
从该站点：
出现交通问题的标准场景是通过连接给定城市集的高速公路网络发送产品单元。每个城市要么被视为“源”，因为单位将从那里运出，要么被视为“汇”，因为那里需要单位。每个源具有给定的供应，每个宿具有给定的需求，并且连接源-汇对的每个高速公路具有给定的单位发货的运输成本。这可以以网络的形式可视化，如下面的图TP-1所示。
给定这样一个网络，感兴趣的问题是确定一个最优的运输方案，该方案在供需约束下最小化运输的总成本。
希望这能有所帮助。
Stack Overflow用户
发布于 2010-05-19 15:23:45
这看起来像是一个标准的Min-cost max flow问题。一个有大约200个顶点的二部图应该很容易在时间上运行。
要创建顶点约束(每个节点只能处理k个人)，您只需创建第二个图G_1，其中为每个v_i添加一个额外的顶点-并使flow v_i To u_i是任何约束，在本例中为k+1，成本为0。所以基本上，如果在原始图G中有一条边(a，b)，那么在G_1中，每条边都会有一条边(u_a，v_b)。实际上，您正在创建第二层顶点，它将每个顶点的流限制为k。
https://stackoverflow.com/questions/2866635
复制
腾讯云开发者
