a********x
发帖数: 1502 | 1 某人要开party，总共有n个人可以选择邀请。举办者知道m对人的两两认识关系。
他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
party的人在party上的陌生人数目也大于或等于5.
问如何选取最大的subset of n 人来参加party。
我能想到O(n^2)的算法。不知道O(n + m)如何解决。 |
g****y
发帖数: 240 | 2 说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
做相同的操作。直到list没有变化为止。感觉复杂度挺高的。 |
a********x
发帖数: 1502 | 3 和你的思路差不多吧。我觉得应该有一些update status的trick能降低复杂度
【在 g****y 的大作中提到】
: 说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
: 把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
: 做相同的操作。直到list没有变化为止。感觉复杂度挺高的。
|
C***U
发帖数: 2406 | 4 不知道题目的意思理解对不对。
是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。
【在 a********x 的大作中提到】
: 某人要开party，总共有n个人可以选择邀请。举办者知道m对人的两两认识关系。
: 他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
: party的人在party上的陌生人数目也大于或等于5.
: 问如何选取最大的subset of n 人来参加party。
: 我能想到O(n^2)的算法。不知道O(n + m)如何解决。
|
a********x
发帖数: 1502 | 5 en
【在 C***U 的大作中提到】
: 不知道题目的意思理解对不对。
: 是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。
|
g****y
发帖数: 240 | 6 展开说说？
【在 C***U 的大作中提到】
: 不知道题目的意思理解对不对。
: 是不是有n个人，然后举办的人知道所有相互认识关系。也就是m对人。
|
C***U
发帖数: 2406 | 7 你这样做不一定最优啊
【在 g****y 的大作中提到】
: 说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
: 把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
: 做相同的操作。直到list没有变化为止。感觉复杂度挺高的。
|
C***U
发帖数: 2406 | 8 我觉得我之前想错了
【在 g****y 的大作中提到】
: 展开说说？
|
g****y
发帖数: 240 | 9 我没说最优啊，这只是我能想到的方法。。。。
【在 C***U 的大作中提到】
: 你这样做不一定最优啊
|
d*****y
发帖数: 1365 | 10 我觉得可以证明是最优的。
【在 C***U 的大作中提到】
: 你这样做不一定最优啊
|
|
|
C***U
发帖数: 2406 | 11 给你个例子
给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
10个组。
然后有单独一个人，他和其他所有人认识。
【在 d*****y 的大作中提到】
: 我觉得可以证明是最优的。
|
c********t
发帖数: 5706 | 12 建一个map, key是认识人数，value是人，就是认识i个人的所有人在一个value
当从list删除这个人的时候，更新他认识的人的list，如果他认识的人变的<5,
recursion 删除这个人，他不认识的人如果是认识总数=n-5的，从map中找到他们
recursion 删除，总人数n--。应该是n+m的复杂度吧
【在 g****y 的大作中提到】
: 说说你的解法？我的解法是，对于每一个人，如果他认识的人数大于n-5或者小于5，就
: 把他从list中删除，同时更新他认识的人的list，更新总人数n。然后再重头开始扫，
: 做相同的操作。直到list没有变化为止。感觉复杂度挺高的。
|
C***U
发帖数: 2406 | 13 你开始怎么选的人?
【在 c********t 的大作中提到】
: 建一个map, key是认识人数，value是人，就是认识i个人的所有人在一个value
: 当从list删除这个人的时候，更新他认识的人的list，如果他认识的人变的<5,
: recursion 删除这个人，他不认识的人如果是认识总数=n-5的，从map中找到他们
: recursion 删除，总人数n--。应该是n+m的复杂度吧
|
d*****y
发帖数: 1365 | 14 OK，初始状态，一共51个人，其中有50个人，每个人和6个人认识，另外一个人，认识
其余50个人。
第一步就是把那个人删掉。
剩下的50个人，没法删除任一个，就是最优解
【在 C***U 的大作中提到】
: 给你个例子
: 给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
: 10个组。
: 然后有单独一个人，他和其他所有人认识。
|
f*****e
发帖数: 2992 | 15 要有数学证明才行，否则只能是猜想。
【在 d*****y 的大作中提到】
: OK，初始状态，一共51个人，其中有50个人，每个人和6个人认识，另外一个人，认识
: 其余50个人。
: 第一步就是把那个人删掉。
: 剩下的50个人，没法删除任一个，就是最优解
|
g****y
发帖数: 240 | 16 哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
【在 C***U 的大作中提到】
: 给你个例子
: 给10组5个点的complete graph。也就是说每个组5个人。然后这5个人相互认识。这样
: 10个组。
: 然后有单独一个人，他和其他所有人认识。
|
y****e
发帖数: 20 | 17 这里问题的本质是，你如何知道第一轮先去掉这个人而不是其他人？简单来说，当存在
两个人都不合格而且认识人数一样的时候（比如有两个人认识所有人），如何选择该先
删谁？
【在 g****y 的大作中提到】
: 哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
: 。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
|
g****y
发帖数: 240 | 18 都去掉。。。。。。
【在 y****e 的大作中提到】
: 这里问题的本质是，你如何知道第一轮先去掉这个人而不是其他人？简单来说，当存在
: 两个人都不合格而且认识人数一样的时候（比如有两个人认识所有人），如何选择该先
: 删谁？
|
g****y
发帖数: 240 | 19 去掉的顺序无关。
【在 y****e 的大作中提到】
: 这里问题的本质是，你如何知道第一轮先去掉这个人而不是其他人？简单来说，当存在
: 两个人都不合格而且认识人数一样的时候（比如有两个人认识所有人），如何选择该先
: 删谁？
|
C***U
发帖数: 2406 | 20 你不能拿特殊的然后说能解决。那我给个别的例子呢?
【在 g****y 的大作中提到】
: 哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
: 。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
|
|
|
y****e
发帖数: 20 | 21 当然有关啊，去掉一个点会改变剩下节点的度，比如A，B都不合格，并且度一样（不是
认识所有人），去掉A点会产生一个原本认识5个人而变成只认识4个人点，但去掉B点则
不会出现，这种情况是很好构造的。
【在 g****y 的大作中提到】
: 去掉的顺序无关。
|
g****y
发帖数: 240 | 22 但是A B早晚要去掉，不合格的早晚不合格，跟你去掉那个没关。既然这么好构造，你
构造一个反例来说明removal order matters
【在 y****e 的大作中提到】
: 当然有关啊，去掉一个点会改变剩下节点的度，比如A，B都不合格，并且度一样（不是
: 认识所有人），去掉A点会产生一个原本认识5个人而变成只认识4个人点，但去掉B点则
: 不会出现，这种情况是很好构造的。
|
g****y
发帖数: 240 | 23 我没有用特例，是你自己说给了反例。。。。。
【在 C***U 的大作中提到】
: 你不能拿特殊的然后说能解决。那我给个别的例子呢?
|
C***U
发帖数: 2406 | 24 而且我的例子 你的解答不对。。。
应该是去掉一个组
然后把剩下9个组和那个人加进来
因为如果把那个所有人都认识的人去掉
别的人只认识4个人 那就是所有人都不能参加了！
【在 g****y 的大作中提到】
: 哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
: 。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
|
C***U
发帖数: 2406 | 25 你的解答是不对的
我的那个例子 应该是46个人是最佳的
而不是50个人。
【在 g****y 的大作中提到】
: 我没有用特例，是你自己说给了反例。。。。。
|
g****y
发帖数: 240 | 26 不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？
【在 C***U 的大作中提到】
: 你的解答是不对的
: 我的那个例子 应该是46个人是最佳的
: 而不是50个人。
|
C***U
发帖数: 2406 | 27 对啊
每个人必须认识5个人才能去聚会
一个组5个人，那么一个人只认识4个人！
【在 g****y 的大作中提到】
: 不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？
|
C***U
发帖数: 2406 | 28 原题要求：
他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
party的人在party上的陌生人数目也大于或等于5.
【在 g****y 的大作中提到】
: 不知道你在说什么，为什么要去掉一个组?你不是说一个组五个人，然后相互认识吗？
|
g****y
发帖数: 240 | 29 你想说明什么？我投降了…
【在 C***U 的大作中提到】
: 原题要求：
: 他想让每个参加party的人认识的参加party的人数目大于或者等于5；同时每个参加
: party的人在party上的陌生人数目也大于或等于5.
|
C***U
发帖数: 2406 | 30 晕
我想说明你给的解答不对啊
那个所有人都认识的人应该参加。。。。
就这么简单啊。。。。
你说的是让所有人都认识的不参加 其余的人都参加
这个解答不符合原题要求 因为剩余的人只认识4个人了
我说的答案是应该让所有人都认识的那个人参加 然后10组里面选9组参加
总共46个人才是正确答案
【在 g****y 的大作中提到】
: 你想说明什么？我投降了…
|
|
|
C***U
发帖数: 2406 | 31 大牛
这个是你给的解答
发信人: gnahzy (hello), 信区: JobHunting
标 题: Re: 问一道算法题
发信站: BBS 未名空间站 (Thu Oct 4 16:30:52 2012, 美东)
哦，你说不优的意思是说解答不对？我还以为你说效率不好呢。你这个例子很好解决啊
。第一轮去掉那个认识所有人的。然后剩下的所有人都符合要求了，直接返回了。
如果不是我理解错你的意思了的话 你给的解答是错误的。。。。。
【在 g****y 的大作中提到】
: 你想说明什么？我投降了…
|
g****y
发帖数: 240 | 32 靠，是我不好。我以为一个小组5个人，每个人就认识5个人呢。但是我的算法没问题。
正确答案是没有人符合要求。你那个46个人不对。因为有一个人认识晚会上的所有人。
【在 C***U 的大作中提到】
: 晕
: 我想说明你给的解答不对啊
: 那个所有人都认识的人应该参加。。。。
: 就这么简单啊。。。。
: 你说的是让所有人都认识的不参加 其余的人都参加
: 这个解答不符合原题要求 因为剩余的人只认识4个人了
: 我说的答案是应该让所有人都认识的那个人参加 然后10组里面选9组参加
: 总共46个人才是正确答案
|
C***U
发帖数: 2406 | 33 好吧。。。我也理解错题意了。。。
我以为是认识的人要少于n-5
不是n-5
是party上的人数-5
才看清楚
【在 g****y 的大作中提到】
: 靠，是我不好。我以为一个小组5个人，每个人就认识5个人呢。但是我的算法没问题。
: 正确答案是没有人符合要求。你那个46个人不对。因为有一个人认识晚会上的所有人。
|
D**f
发帖数: 439 | 34 我的想法是这样的：
先扫描全部人，排除所有认识人数小于5的（可以证明包括他们的解是错误的）
再扫描剩下的人，（其实可以合并到第一趟扫描里面）
每扫描一个人，记录当前扫描到的人数，记为X，当前认识人最多的那个人认识Y个人，
只要扫描到符合如下condition的节点就可以返回了：
X>Y+5， 如果扫描完了还不符合，就是没有。
可以证明有返回结果肯定是对的，但是没找到是不是就一定没有，还得证明一下。 |
C***U
发帖数: 2406 | |
