作者puzzlez (帕索)
看板puzzle
标题[问题] 聚会的讨厌对象
时间Mon Sep 12 13:40:35 2011
这是帮某人代po的文章：
假设有1号到100号总共100个人，
每个人都有一些固定讨厌的对象。
每个人讨厌的人数都不一定，每个人都不讨厌自己。
例如12号讨厌3个人，18号讨厌6个人之类的。
而每个被讨厌的人也都一定讨厌那个讨厌他的人。
（也就是说，在这个题目里面「讨厌」这个关系是对於双方都成立的。
若3号讨厌8号跟16号，那麽8号跟16号讨厌的人里面也一定有包括3号。
若a讨厌b.则b也一定讨厌a）
我不属於这100个人里面，我知道所有人他们所讨厌的人的名单。
现在我的目标是要邀请到最多人数的人来参加聚会。
邀请的对象是谁不重要，重点是「邀请到最多人数，这些人彼此都不讨厌对方」。
有什麽好方法可以简单找到能邀请到最多人数的群体吗？
--
~帕索板四徵兆~ 战略高手 游戏, 数位, 程设
PlayingGame 游戏 Σ游戏 棋艺 桥牌
谜 ○ ！ * \○/ ★ (○ ？ Puzzle 益智 ◎
╦╦└□ " ○□═ □ □>
║║√√ ╦══╦ ∥ |\ 欢乐帕索板
上Ｂ爱解谜 睡着还惦记 解完好开心 卡解伤脑筋 欢迎你一起来玩ψmaplemiracle
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.194.43.107
1F：推 arthurduh1:邀到的人群里面要有什麽限制好像没讲欸...? 09/12 13:43
2F：→ arthurduh1:是不互相讨厌吗? 09/12 13:44
3F：推 LPH66:这个是计算机科学里所谓的 maximum independent set problem 09/12 13:56
4F：→ puzzlez:我也重覆看了好几次....结果发现我看不懂....囧 09/12 15:22
5F：推 arthurduh1:如果是的话就是LPH66大说的那样没错XDDD 09/12 15:33
6F：→ puzzlez:所以 L 大 那样算回答了问题了吗？ 09/12 18:23
7F：推 LPH66:那句话的潜台词是「这问题目前没有"有效"解法」... 09/12 19:40
8F：→ LPH66:以电脑程式(或更广义叫演算法)来计算的话 09/12 19:42
9F：→ LPH66:所需时间会随着人数增加而成指数成长 09/12 19:42
10F：→ caago123:每个人讨厌的人的人数不固定 <-- 这句是什麽意思?? 09/12 19:43
11F：→ caago123:讨厌的人数会变动?? 09/12 19:44
12F：推 LPH66:我猜这只是指像某A讨厌三个某B讨厌四个这种数量不等的情形 09/12 19:45
13F：→ puzzlez:我来改好了.... 09/12 19:52
※ 编辑: puzzlez 来自: 123.194.43.107 (09/12 20:10)
14F：推 joeyeh:贪婪法不是n平方? 09/12 23:05
15F：推 joeyeh:邀请的情况是找100减M.I.S.(找差集合)? MISP是NPC问题阿 09/13 07:41
16F：推 joeyeh:但还是再找剩下中的MIS直到没有"讨厌"情况存在为止 09/13 07:47
17F：推 walkwall:所以说最佳解没有有效解法 找近似解的有效算法比较可行 09/13 10:55
18F：推 e7410akgb:应该是每个人所讨厌人的人数都不一定"相同" 01/04 16:22