切换到宽版
  • 4034阅读
  • 0回复

求助!!!!! NOIP2007提高组第四题 [复制链接]

上一主题 下一主题
离线tmy9154
 
只看楼主 正序阅读 0 发表于: 2007-12-02
题目中已经说了,如果有多条直径的话他们的中心也一定重合,换言之一定至少有一个节点或一条路径重合。假设有两条直径分别为AB和CD,它们重合的部分是
EF。那么一定有AE的长度等于CE的长度,FB的长度等于FD的长度。其次核一定是在直径的中央部分。下面分两种情况讨论: 1.
如果给定的s能够覆盖重合的点或者路径,那么我们在任一条直径上选择一个核,那么对于另外的直径而言,就是只选择了重合的部分,对于这个核的偏心距"有贡
献"的只可能是在非选中的直径上,而对于每条直径除去重合部分剩下的两部分的长度都是相等的,所以选择任意一条直径均可。 2.
如果不能覆盖,那么对于所有直径选择的部分都是相同的了,更是可以任选了。 两点还可以改进的地方,由于数据不是很强,我也就没改
核一定是在直径的中央部分,所以可以从直径的中心向两边扩展求核



可以证明的是,如果图中存在多条路径,则在任何一条直径上都存在一条core(反证法,用到直径的距离最大性)。





能不能帮我我解释一下上面拿两个是什么意思?有点搞不懂。谢谢!
快速回复
限100 字节
 
上一个 下一个