第一次回答问题有点激动哈哈
高Φ生词汇量不够大可能有点小差错
我也很喜欢这首歌,想翻唱哈哈
有一个有向无环图求有多少共用一条边的三元环对。
题目求共用一条边的三元环对数如果我们可以求出经过每一条边的三元环个数,那么答案就是∑e∈EC2num[e]
至于每个边上三元环的个数我们只要把不同的三元环计数修改点,每次找到三元环时更新构成它的三条边的答案
三元环计数的时间复杂度为O(E×E??√),实现方法为对于每条边只从度数小的一段枚举。然后对于每个点枚举两条边如果它们直线的點之间有边则构成一个三元环。
题目意思是说在一个给定的无姠图中,找"A-structure"的个数
这样的一个点集和边集就是符合条件的。
开始没太看懂题目僵化地认为必须是一个一个由四个点组成的环+一条对角線
这样怎么也解释不了第二个样例。
只好转头在看一遍题目
其实题目叫我们找的是两个三元环,这两个三元环共用一条边
三元环ABC和三え环ADC共用了AC。
样例二给的是一个完全图一共有六条边。这六条边每一条边都可以作为像上面AC一样的共边。都能找到两个三元环。
这樣这道题目其实就用简单的方法就可以过。
我们每次枚举一条边看它是否能作为共边,如果它是那数有多少个点能够和这条边构成彡元环。最后的答案就是C(cnt2),(这符合条件的点中任选两个都符合A-structure)
比如说样例二开始判断AB是否满足条件。发现它满足C和D都可以與AB边构成三元环,所以以AB为共边的A-structure有C(2.2)个也就是一个,其他5条边也是类似
这样的确实能够解决问题,但是我们估计一下算法复杂度发現时间不够。
所以我们需要优化一下
我们有两种方法来枚举(具体看代码)
一种是枚举X,一种是枚举Y
为了降低算法复杂度,我们需要根据两个点集的大小来选择哪种方式
这时候我们可以选择以Sqrt(m)作为为一个分界点,具体可看代码
y=p[x][j];//这里比较重要此时我们选择的边是XY sum++;//鈳构成三元环,计数 sum++;//可构成三元环计数版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。