• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1129 – Channel Allocation

    ACM-POJ EXP 194阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大概题意

    当一个广播电台在一个非常大的地区,广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而,每个中继器必须慎重选择使用,使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道,那么就不会相互干扰。

    由于无线电频道是一有限的,一个给定的网络所需的中继频道数目应减至最低。编写一个程序,读取一个中继网络,然后求出需要的最低的不同频道数。

    建模

    一个有N个节点的无向图,要求对每个节点进行染色,使得相邻两个节点颜色都不同,问最少需要多少种颜色?

    那么题目就变成了一个经典的图的染色问题。

    解题思路

    对于这题数据范围很小(节点最多26个),所以使用普通的暴力搜索法即可

    对点i的染色操作:从最小的颜色开始搜索,当i的直接相邻(直接后继)结点已经染过该种颜色时,搜索下一种颜色。

    就是说i的染色,当且仅当i的临近结点都没有染过该种颜色,且该种颜色要尽可能小。


    要注意题中的一句话

    since the repeaters lie in a plane, the graph formed byconnecting adjacent repeaters does not have any line segments that cross.

    大致意思就是 “城市所在的世界是一个平面世界,当把城市看做点,相邻城市用边连接时,这些边不能相交


    PS: 在网上很多同学都说用“四色定理”解决这题, 其实不是,四色定理在本题单纯是用来剪枝的,而且由于结点数较少(只有26),剪枝与否对时间影响不大,普通的爆搜也是0ms AC的,不过有兴趣的同学可以看看“四色定理”。

    因为当结点数很多时,四色定理的剪枝优势就会体现出来了

    我把 暴力搜索经过四色定理剪枝的搜索 两个程序都都贴出来,大家比较一下就知道四色定理怎么用了。

    四色定理的“相邻”是指两块多边形地区“至少一条边重合”才为之相邻

    “至少一条边重合”同时也隐含了“任意边(线段)不正规相交

    如:

    再反观本题的模型,本题的相邻是“两点有边连接,但任意两边不交叉(正规相交)”,这种“相邻”其实就是四色定理的“相邻”。

    我举一个例子就一目了然了:

    N=7

    A:BCDEFG

    B:ACDEFG

    C:ABD

    D:ABCE

    E:ABDF

    F:ABEG

    G:ABF

    画成图就是:

    PS:由于边不允许相交,这已经是7个点的最大连接数

    四色定理的原始理论依据

    对于一个散点集,若要求尽可能连接任意两个点,但任意一条边边不允许与其他边相交,

    那么当散点集的元素个数<=4时,连接所得的图必为一个一个 无向完全图

    当散点集的元素个数>4时,连接所得的图必不是一个完全图

    完全图:任意两点均相邻

    最后千万要注意输出,当频道数大于1时,channel为复数 channels


    方法一: 四色定理剪枝的搜索

    转载请注明:EXP 技术分享博客 » POJ1129 – Channel Allocation

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址