确定是否可以将所有用户连接到蜂窝塔?[多项式时间算法]

Question

给定：
用户u1，。。。，嗯
为每个用户提供：用户可以连接的蜂窝塔列表{s1，…sn}

蜂窝塔c1，。。。。cn
每个单元塔给出：容量cp

问题：是否可以在不超过容量的情况下将所有用户连接到蜂窝塔

我的方法：

if sum(total_cell_capacity) < sum(total_users): 
    return false  #Joy Z's idea
sort users by number of available towers to them (ascending order)  
for each user:
    if user only have one tower availble to them:
        if tower is not full:
            allocate user to the tower
            tower_capacity --
        else:
            return false
    else:
        choose cell tower with biggest current capacity:
            allocate user to the tower
            tower_capacity --
return true

这会产生多项式时间吗？这个算法至少能解决问题吗？

*我正在努力学习如何在stackoverflow上写得更好
*请纠正我犯的任何错误。

提前谢谢。

Answer 1

这简化为最大基数匹配问题，并且可以使用Hopcroft-Karp算法在O（maxCp-mn-Sqrt（m+maxCpn））时间内解决。如果maxCp是有界的，则减少到O（mn-Sqrt（m+n））。

详细地说：定义一组用户节点U={u1，u2，..，um}和一组蜂窝塔槽节点

C = {c11, .., c_{1,cp(1)}, c_{2,1}, .., c_{2,cp(2)}, .., c_{n, 1}, c_{n, cp(n)}

现在，在每个用户节点和她可以连接的每个蜂窝塔槽的节点之间添加一条边，形成一个二分图。然后，您的问题简化为图中匹配的最大基数是否为m大小的问题。如果是，每个用户都可以连接到某个蜂窝塔插槽。如果不是，它必须小于m（不能更多，因为我们只有m用户节点）。

给定V节点和E边的二分图，Hopcroft-Karp算法解决了时间O（ESqrt（V））中的最大基数问题。由于我们最多有maxCp-mn边，最多有maxCp n+m节点，因此我们得到O（maxCp-mn-Sqrt（maxCp n+m））的运行时。

Answer 2

我认为这又是分配问题。每个用户都是需要做的工作。对于每个细胞塔，根据其容量创建一定数量的工作人员。用户可以连接到的蜂窝塔列表告诉你哪个工人可以做哪些工作而不会受到惩罚。http://en.wikipedia.org/wiki/Assignment_problem告诉你如何解决这个问题/尽量减少处罚，例如匈牙利算法。