use*_*643 5 c++ algorithm graph dynamic
我有一个多个"动物笔"的加权图,每支笔至少有3个边/点和至少两个笔.我必须弄清楚要移除的最小加权边缘以便连接所有笔(您可以通过移除未连接到其他笔的外边缘来连接它们).
有人可以推荐一个算法或一个过程,我可以用它找到最小的加权墙去除.我在考虑Prim的算法,但我甚至不确定如何应用它.
这是问题S4 http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf
我不希望答案只是如何处理它的方向
你是在正确的方向.
建模您的问题,为无向图G=(V,E),其中V = { all pens },E = { (u,v) | there is a wall between u and v }与w((u,v)) = cost of wall between u and v
为了"连接所有笔" - 你实际上正在寻找一个子图:G'=(V,E')这样子图G'将被连接[每两个节点之间有一条路径],并且E'中的墙的成本是最小的.
要以最低的成本获得这一点 - 您正在寻找最小生成树.[很容易看出你确实需要一棵树 - 因为在创建树之后任何额外的边缘是多余的并且可以在不损害图形连接的情况下移除 - 或者在问题术语中 - 你可以恢复一面墙并且笔将会保持联系]