CF1450E Capitalism

整个社会可以用一张由 $n$ 个顶点和 $m$ 条边组成的无向联通图来表示。顶点代表人，一条边 $(i,j)$ 代表人 $i$ 和 $j$ 之间的友谊。 在社会上，第 $i$ 个人有收入 $a_i$。一个人 $i$ 羡慕一个人 $j$，等价于 $j$ 比 $i$ 多出1个单位的收入，也就是 $a_j=a_i+1$。 如果对于每一对朋友，都有一个人羡慕另一个人，这个社会就叫资本主义社会。对于一些朋友关系，你知道哪个人在羡慕另一个人。对于其余的朋友关系，你不知道谁羡慕谁。 社会收入不等值的定义是：$\max_{i=1}^na_i - \min_{i=1}^na_i$，也就是社会中收入最多的人的收入与收入最少的人的收入之差。 你只知道一些朋友关系，不知道每个人的收入。对于一部分朋友关系，你知道谁羡慕谁；对于另外一部分，你不知道。你要判断这个社会是否可能成为资本主义社会。如果是，你要构造一个 $a$ 满足所有条件，且这是个资本主义社会。要求你给出的 $a$ 让社会收入不等值最大。

无

无

In the first test, we can show that an income inequality greater than $ 3 $ is impossible for the given society. In the given answer with income inequality equal to $ 3 $ : - Person $ 2 $ is envious of person $ 1 $ . - Person $ 3 $ is envious of person $ 2 $ . - Person $ 5 $ is envious of person $ 2 $ . - Person $ 6 $ is envious of person $ 5 $ (the required direction is satisfied). - Person $ 6 $ is envious of person $ 3 $ . - Person $ 2 $ is envious of person $ 4 $ (the required direction is satisfied). In the second test, we can show that there is no way to assign incomes to satisfy all requirements.