特邀出题人MACW题解：原链接
题目解析
题目问最多可以获得的额外伤害，其实就是询问在这些技能中，如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点，把每一个攻击加成看作图的边，权制为 Ei,jEi,jEi,j。由于 Ei,jEi,jEi,j 与 Ej,iEj,iEj,i 相等，则可以将这个图视为无向图。 可以样样例抽象成下图：
考虑使用贪心的思想来解决本题，每次在图中找到权值最大的一条边选择即可，但图中不能出现环。因为是无向图，在考虑的时候可以忽略技能使用的顺序。接下来就是找一个最大生成树即可。
AC代码
时间复杂度分析
本道题可以使用最小生成树Kruskal算法来实现，将题目的模型抽象化后可以被看作为一个最多有 (1+n)∗n2−n\frac{(1+n)*n}{2} - n2(1+n)∗n −n 条边的无向图（化简后可得 n2−n2\frac{n^2 - n}{2}2n2−n )。注意一开始需要对每一条边进行排序。本道题的时间复杂度约为 O(2×n2log2n)O(2\times n^2 \log_2{n})O(2×n2log2 n)。
