最近还在搞 SC AI。

由于每个单位仅能攻击敌人，所以其攻击链类似一个树（其每一个节点都是多源单汇的，类似于树的有一个父亲但有多个儿子的情况）。唯一不同的是这个树的树根也可能攻击一个敌人，从而形成环。但是由于一个单位只能攻击一个敌人，所以在一个独立的联通分量里面，最多只有一个环。

现在我在考虑使用递归来遍历这个图，然后得出每个单位在目前情形下再有多少轮会被消灭的报告。之所以要遍历，是因为有这种情况：a攻击b。c和d都攻击a。b攻击a。c和d又各自同时被两个单位攻击。在这种情况下，表面上看a遭受的攻击最多，他应该选择撤退。但是假如考虑到c和d的血量，或许c和d会在a之前被消灭。之后a遭受的攻击就不比b多了。所以在某种情况下，a应该采取的策略是继续进攻而不是撤退。

以上是我决定计算攻击链的理由。

于是在采取递归遍历这个图的时候，关键问题是怎样避开这个环。首先是如何发现这个环，然后是如何处理他。关于发现，我现在采取了一种非常低级的办法。我使用了一个静态的数组，记录每一次递归遍历到的节点。假如下一次递归遇到了这个数组里面的节点，则表示发现了环，并开始调用处理环的函数。我相信关于发现环一定有更好的算法。可惜暂时没有时间做了，加上问题都是节点数量在20以下的，所以也没有必要做得很复杂。
至于处理环的方法，我决定在这个环上寻找最早被消灭的节点。由于仅可能有一个环，所以先把除了环之外的分支计算完毕，之后将这些分支的贡献都先计算掉。此时得出的最先被消灭的单位，在环贡献也计算的情况下一定也是最先被消灭的。因此此时可以先计算这个节点的消灭轮次，然后在这个位置将环打开，并按照无环的逻辑去计算每一个节点。

这个问题抽象出来是个很有趣的图论问题，今后应该可以继续深入思考他的意义，并跟其他图论问题做一些比较，不过暂时先放在这里吧。