 ONLINE |
wutiantongV2EX 第 156258 号会员，加入于 2016-01-20 18:10:09 +08:00今日活跃度排名 3680 |
wutiantong 最近回复了
2 天前 回复了 Heiban 创建的主题 › 问与答 › 不会拒绝别人，太 sb 了。 |
确实 sb
4 天前 回复了 zhanglihow 创建的主题 › 问与答 › 听说公司之前有员工上班打卡用虚拟定位被开除的，是怎么被发现的？我有点慌
PS:公司是用单独的一个办公 App 定位打卡的，我是用 xposed 的方式虚拟定位，再通过 App 定位打卡。 |
本来没事，在这一问然后被老板看到开除了。
7 天前 回复了 lunar96 创建的主题 › 问与答 › 秋天来了，哪儿有比较好的赏桂地点，坐标无锡，高铁一小时内都可以接受 |
@lunar96 南京中华门城墙附近是有很多桂花树的，免费公园。
7 天前 回复了 lunar96 创建的主题 › 问与答 › 秋天来了，哪儿有比较好的赏桂地点，坐标无锡，高铁一小时内都可以接受 |
无锡没有桂树么？在南京生活倒是经常能闻到桂花香。
8 天前 回复了 ofooo 创建的主题 › 程序员 › 原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少 |
@inu1255
他这个算法额外引入了对元素顺序的依赖（从前向后遍历），仍然是一个 trivial 的贪心算法，不是最优解。
他这个算法额外引入了对元素顺序的依赖（从前向后遍历），仍然是一个 trivial 的贪心算法，不是最优解。
8 天前 回复了 ofooo 创建的主题 › 程序员 › 原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少 |
@ofooo 主体计算复杂度就是找出图的 conneted components。
在第 0 步中包含了一次这个计算，针对的是 N 个节点的图。
在最后一步中也包含了一次这个计算，针对的是 O(N*N) 个节点的图。
在第 0 步中包含了一次这个计算，针对的是 N 个节点的图。
在最后一步中也包含了一次这个计算，针对的是 O(N*N) 个节点的图。
8 天前 回复了 ofooo 创建的主题 › 程序员 › 原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少 |
@ofooo 多项式量级。
8 天前 回复了 ofooo 创建的主题 › 程序员 › 原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少 |
@aijam 看我上一条的图解法，我觉得好像没问题了。
8 天前 回复了 ofooo 创建的主题 › 程序员 › 原创算法题: 把有互斥条件的多个元素分组, 如何保证组的数量最少 |
@wutiantong 我觉得我这个思路还可以抢救一下：
0. 首先我们要扩展补充 (complete) 所有（显式或隐含定义的）互斥二元组。
0-1. 比如说，假如给定(1, 2), (2, 3) 为互斥关系，那么(2, 3) 也是一个(隐含的)互斥关系。
0-2 从图的角度来说，任何两个元素只要有路径(path)连接，就应确保它们之间有一条直接的边(edge)。
1. 把(a, b) 二元组当作节点，其中 a 不等于 b，总共 n*(n-1)/2 个节点。
2. 在(a, b) 与 (b, c) 之间连线。
3. 从图中删掉所有（显式或隐含定义的）互斥二元组对应的节点。
4. 答案是剩余图的 connected component 个数。
0. 首先我们要扩展补充 (complete) 所有（显式或隐含定义的）互斥二元组。
0-1. 比如说，假如给定(1, 2), (2, 3) 为互斥关系，那么(2, 3) 也是一个(隐含的)互斥关系。
0-2 从图的角度来说，任何两个元素只要有路径(path)连接，就应确保它们之间有一条直接的边(edge)。
1. 把(a, b) 二元组当作节点，其中 a 不等于 b，总共 n*(n-1)/2 个节点。
2. 在(a, b) 与 (b, c) 之间连线。
3. 从图中删掉所有（显式或隐含定义的）互斥二元组对应的节点。
4. 答案是剩余图的 connected component 个数。
Select Language