切换到宽版
发帖 回复
返回列表
  • 5276阅读
  • 0回复

难题！！计算无根书的最小支配集--火力中心布局 [复制链接]

 上一主题 下一主题
离线zqbnew
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2009-09-27
                                   火力中心布局
       现有一张由n个堡垒组成的交通图，任意两个堡垒之间只有一条通行路线。为了确保路线畅通，必须在某些堡垒上建立火力中心，每个火力中心都能够对其相连的所有交通线进行全天候的监控，防止敌人侵略。现在的问题是如何设置火力中心的布局，才能用最少的火力中心控制所有交通路线。
输入：堡垒数n(1≤n≤10000)；以下每行为i，j，表示堡垒i与堡垒j连接。以0 0标志结束；
输出：
   w行，每行为火力中心所在的堡垒号。最后一行为火力中心数w
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个