这次比赛 GCC 只能说是发挥得一般。一共出了5个题，排名第9。感觉上还 1007 应该能出的。如果做出6题，排名能到第4，那就很好了。

这次比赛有两个题目比较好：1007 和 1009。1007 没能 AC。1009 经过我和 mmd 的讨论，最后 AC 了。

我简单地说一下这两个题目的做法。
amath
1009：题目给出`n`个任务，每个任务要么提前完成，花费代价`a_i`，要么推迟完成，花费代价`b_i`。另外给出一个有向图关系，边`A -> B`表示如果任务`A`推迟完成，那么任务`B`也要推迟完成。求完成这些任务的最小代价，并在花费代价最小的前提下，求出提前完成任务数量的最大值。

我的想法是，给每个任务定义一个值`w_i = b_i – a_i`。那么最小代价就是`sum(w_j) + sum(a_i)`，其中`sum(w_j)`表示推迟完成的任务的`w`值之和，`sum(a_i)`表示所有任务的`a_i`值之和。因为 `sum(a_i)`为定值，可令`sum(a_i) = s`。我们的目标就是求`sum(w_j) + s`的最小值，也就是求`sum(w_j)`的最小值，即`sum(a_i – b_i)`的最大值。

我们定义闭合子图是一个图的子图，满足子图中每个点的后继都在子图中。那么最大权闭合子图就是一个图中顶点权值和最大的闭合子图（注意点权可以有正有负）。那么刚才转化出来的模型就是要求一个以`sum(a_i – b_i)`为点权图的最大权闭合子图。

求最大权闭合子图有一个最小割算法。从源点`s`到每个正权点连一条边，容量为点的权值，从每个负权点到汇点`t`连一条边，容量为权值的相反数。保留原图中的所有边，其容量设为无穷大。这个网络的最小割就对应最大权闭合子图。正权点的权值之和减去最小割容量就是最大权闭合子图的权和。这样我们就解决了第一问。

第二问要求在花费代价最小的前提下，提前完成任务数量的最大值。我们在跑完最大流的剩余网络中，从源点`s`开始遍历，记录遍历到的点的个数，也就是推迟完成的任务的个数，用总任务数减去它就是第二问的解。

1007：题目给出空间中`n`个点，要求一个点（不一定是这`n`个点中的点）使得这个点到`n`个点的欧几里德距离之和最小。

当时比赛的时候没有做出来，今晚我们又讨论了一段时间，最后我去写了个调整的算法 AC 了。

具体做法是，任取一个点，设步长为`step`，看看这个点往`6`个标准方向移动`step`之后，到`n`个点的距离之和会不会减小。如果会减小，就移动这个点。如果`6`个标准方向均不能使距离和减小，就减小 `step`。这样一直迭代下去，直到精度符合题目要求为止。具体`step`和`step`减小的方式要看数据而定。对这个题目，我们的`step`是`1000`，`step`减小的方式是每次变为原来的`0.799999`倍。初始点为`(0, 0, 0)`。实验发现，对于`(0, 0, 0)` 这个初始点，`step` 每次缩小到`0.8`倍不能得到样例的最小值…这说明此问题可能存在多个极值。遇到这种情况，可以用随机化解决，也就是多次随机取初始点，再选取最优解。p.s. 我比赛的时候试图用遗传算法解决这个问题，但精度不够，WA。原因是遗传算法产生的解可能是在最优解附近小幅度波动的。
endamath