首页 > 代码库 > 竞赛图如何构造三元环
竞赛图如何构造三元环
讲解视频
一场NOIp模拟赛的T3里看到的一个东西,因为那道题目不开放评测,所以简单写一下。
假设存在这样一张竞赛图,其中存在这样一个环
$node_a \rightarrow node_b \rightarrow node_c \rightarrow node_d \rightarrow node_e \rightarrow node_a$
首先明确,这是一个竞赛图,对于任意的$node_a$和$node_b$,要么存在$node_a \rightarrow node_b$要么存在$node_b \rightarrow node_a$。
我们的目标是在一个竞赛图中构造三元环,根据这个方法,我们就可以使用$Tarjan$算法把任意大小的环构造成三元环。
一些具体的步骤
定义环的大小为$tol$,那么上述的环$tol=5$,目标是把$tol$变为3,一个方法是在环中找到一个$tol=3$的环,一个方法是不断删点,最终删到$tol=3$
我们同时进行这两个方法。
再回到上面的性质:
对于任意的$node_a$和$node_b$,要么存在$node_a \rightarrow node_b$要么存在$node_b \rightarrow node_a$
首先对于$node_a \rightarrow node_b \rightarrow node_c$
必定存在$node_a \rightarrow node_c$或者 $node_c \rightarrow node_a$
对于第一个,我们可以将$tol--$,对于第二个,显然找到了一个$tol=3$的环,
然后继续执行下去就行了。
竞赛图如何构造三元环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。