📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
123
返回列表 发新帖
楼主: PincessR
跳转到指定楼层
上一主题 下一主题
收起左侧

[入门|算法|数据结构] 算法可第三周的编程作业题讨论

🔗
麻倉枼 2014-5-30 10:08:43 | 只看该作者
全局:
breezet 发表于 2014-5-29 20:21
其实我觉得你在15楼提到的整体思路不是很清楚,容易带来问题。。。如果单纯的看这一部分,倒没有什么问题 ...

我的结构是用hashmap的,
其实我也有key list,
然后就是bug让我找到了,压根不是逻辑问题而是别的,
另外就是现在解决这个bug发现Min cut 数字很大啊,最低极限是20,无法突破到17。。

我举个例子吧。。
V       E
1        2        3        4        7       
2        1        3        4       
3        1        2        4       
4        1        2        3        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7       

Round 1:
mainVertex = 2
subVertex = 3

step 1: add all subV EdgeList to mainV
V       E
1        2        3        4        7       
2        1        3        4        1        2        4
3        1        2        4       
4        1        2        3        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

step 2: remove subV from the graph
V       E
1        2        4        7       
2        1        4        1        2        4
4        1        2        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

step3: removed self loop from each edgeList, current mainV = 2
V       E
1        2        4        7       
2        1        4        1        4
4        1        2        5       
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

IMPORTANT STEP: modify each subV that is in the mainV edgeList, count how many of each, and then modify its edge list; EX: 1 在 2的edgeList 出现两次,所以我们跳到1的edge list 数有多少个2, 如果少过两次的话,加2直到有两次为止;然后如此类推

V       E
1        2        4        7        2
2        1        4        1        4
4        1        2        5        2
5        4        6        7        8       
6        5        7        8       
7        1        5        6        8       
8        5        6        7

End of Round 1
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表