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