黑车店面

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

giggoug 发表于 2020-11-6 14:52
怎么优化呢？

核心问题在于找出强链接的vertex，用tarjan可以在O(n)复杂度中找出来，之后根据强链接点算出不同的group，再按照0号感染者排序两边走，找出移除哪一个强链接收益最高

楼主的union find是不是有corner case
比如 三个感染者 两个在一个set里面 set里面50人
剩下一个感染者 在size是两个人的set里面 应该删除掉最后一个感染者 而不是最大set的

补充内容 (2020-10-30 17:13):
啊 抱歉 漏看了一句话

Roc1mu3fen 发表于 2020-11-4 03:35
follow-up楼主的解法貌似不行吧，因为涉及到connectivity。举个例子：
x o o    o o x
o o o x o o o

那个matrix是contact matrix， 不是说一开始谁感染了谁没感染

Roc1mu3fen 发表于 2020-11-4 03:35
follow-up楼主的解法貌似不行吧，因为涉及到connectivity。举个例子：
x o o    o o x
o o o x o o o

那个matrix是contact matrix， 不是说一开始谁感染了谁没感染

Roc1mu3fen 发表于 2020-11-4 14:00
对的是contact matrix。我画的图是表示实际上的图，o/x表示人，x表示那个人是initial感染的。中间那个x链 ...

按照你这个解释就变成NPC问题了，要计算所有可能的解

giggoug 发表于 2020-11-05 22:27:55
按照你这个解释就变成NPC问题了，要计算所有可能的解

不啊，暴力解也就是把每个人删掉dfs看看最后少了多少感染的而已。

Roc1mu3fen 发表于 2020-11-6 14:31
不啊，暴力解也就是把每个人删掉dfs看看最后少了多少感染的而已。

怎么优化呢？

用tarjan algorithm，找到所有的强连接点，再推算出移除每一个强链接点的结果就可以了。