luogu#P5085. 大奔的方案
大奔的方案
题目背景
题解:https://blog.csdn.net/kkkksc03/article/details/83188325
五个海盗抢到了 个金币,每一颗都一样的大小和价值连城。
他们决定这么分:
- 抽签决定自己的号 ;
- 首先,由 号提出分配方案,然后大家 人进行表决,当且仅当不少于半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
- 如果 号死后,再由 号提出分配方案,然后大家 人进行表决,当且仅当不少于半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。
- 以此类推……
每个海盗都是很聪明的人,他们遵循如下原则:
- 保命;
- 如果满足条件 ,那么想办法获得更多的钱;
- 如果满足条件 ,那么想办法杀更多的人。
那么最终的分配方案会是怎样的呢?
海盗们让小奔求出:若是 个海盗抢到了 个金币,并且要不少于 的人投赞成票,他们会如何分配呢?
请你给出 个海盗分 个金币且要不少于 的人投赞成票的解法,并保证结果号码较小的分到的金币尽可能的多。
但是,现实中并不会那么过于残忍,每个海盗也拥有自己的帮派,同一个帮派的人会互相投赞成票。
作为友情的代价,那个人必须分自己帮派里的每个人一定的金币,如果有一个人(不包括自己)没有被满足,那么整个帮派的人会同时投反对票。
新的结果又会是如何呢?
题目描述
如果 A 和 B 是朋友,B 和 C 也是朋友,那么说 A、B、C 都是同一个帮派里的。
现给出 个兄弟关系,请你弄清其中的帮派关系,再求出 个海盗分 个金币的最新方法。
毒瘤预警:
当然,你仍然需要保证结果号码较小的分到的金币尽可能的多,哪怕破坏帮派之间的关系。(自行理解)
输入格式
第一行,五个数 之间用空格隔开,分别表示强盗数目,金币数目,最低赞成百分比,兄弟关系总数以及所谓的友情所需要的代价。
接下来 行,每行两个数,,表示 和 是兄弟关系(或是说在同一个帮派)。
输出格式
只有一行, 个数之间用空格隔开,表示最后的结果。
如果某个海盗死了,输出 代替。
5 7 50 2 1
1 2
3 2
5 1 1 0 0
提示
数据范围及约定
对于100%的数据:,,,,。