2016-C02-team2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run Id||Problem||Time||Status||
||4||A: Lobby||12||Yes||
||12||B: Cameras||18||No - WA||
||15||B: Cameras||21||Yes||
||35||F: Funfair||36||No - WA||
||41||F: Funfair||44||No - WA||
||45||F: Funfair||56||Yes||
||50||I: Cafebazaar||67||No - WA||
||53||H: DNA Sequencing||78||Yes||
||69||G: Beehive||113||No - WA||
||72||G: Beehive||124||Yes||
||74||I: Cafebazaar||127||Yes||
||87||J: Fence||157||Yes||
||101||E: Billboard||211||No - TLE||
||118||E: Billboard||261||Yes||
||140||C: Robot||298||No - TLE||
== 流水账 ==
=== TsReaper ===
今天学长们会做的题最后都答对了，还是比较理想的。前期简单题'''A1y12'''，B题出现了一些失误，把1~9看成了0~9错了一次，'''B2y21'''。一段时间后hzf学长发现I题是比较经典的网络流，我就在Starve学长想F的时候上机先抄模板。Starve学长也很快想到了F的做法，改了两次错后'''F3y56'''。
不久后我的I题也写好了，但是并没有答对。我觉得模板和构图应该并没有错，只能自己先在一边debug，学长们讨论其它题的做法。学长们很快想到了H的做法，'''H1y78'''，继续思考G题。Starve学长想到把图放进一个坐标系里考虑，并猜出了一些结论。我认为这个结论可能并不正确，想让学长写稳一点的bfs~~幸好学长并没有听我的~~。Starve学长写题的过程中我和hzf学长debug I，学长发现我的做法是最大费用最大流，并不是最大费用流，背了一个锅...Starve学长'''G2y124'''后，我修改了一点代码，'''I2y127'''。学长们又发现J题是一个比较简单的凸包题，'''J1y157'''。
最后只剩下CDE三道题了，我们权衡之后觉得C和E可以尝试一下。我先想到了C题的一个做法，但是实现起来非常麻烦，不过学长们E题也还没有想好，我就先上机写。不久学长们想到了E题O(n^3^logn)的做法，手写了可删除的堆后'''E2y261'''，非常稳。最后40分钟我强行写了C，并没有答对。
=== 3z ===
感觉今天发挥不错，虽然有一些代码失误，但是没有出现未知错误改不出来的情况。
=== hzf ===
今天学长们都好强...我又打了一发酱油...前期看到J，感觉像个凸包＋贪心，继续看I，像是个网络流二分图之类的，但是我不会处理下限...看H，感觉是个trie加个贪心什么的？但是我都没有具体的思路，tsr血行告诉我G可能比较好做，想叫我找个结论..然而我思路错了，推了一些复杂的公式，还是starve学长比较强...建立了正确的坐标系，猜到了正确的结论...过了这道题，期间我和tsr学长讨论了一下I，发现这道题不用保证流量最大，直接求费用最大即可，tsr学长很快找出了一个spfa最大流的性质：每次spfa得到的最长路不增，利用这个性质在spfa得到非正路径时结束算法即可...很强！
之后starve学长把J写了，很顺利。于是只剩下CDE，starve学长先叙述了一下E，并告诉我他的做法...我觉得很科学...但是不好维护。后来tsr学长和我看C，发现关键是怎么判断两个点在不经过某个点的情况下是否联通，~~实际上是个双连通分量...~~，学长希望在tarjan算法求割点的基础上做一些改动，但是很复杂...这时候starve学长E乱搞失败，下来换tsr学长写，不久Starve学长想出了E的正解：把尺取法对象换为行并用两个堆维护前k大数，复杂度比较科学了，正好tsr学长写不下去了...于是换starve学长继续写E，这段时间我和tsr学长又想了想C，但是编程复杂度还是比较高，还看了D，但是没有靠谱的做法...很快starve学长过了E，之后tsr学长一直写C直到结束...
== 总结 ==
=== TsReaper ===
* 简单题还是WA了，很亏...
* 对网络流没有理解充分，混淆了最大费用流和最大费用最大流。大概需要网络流24题搞一波...？
=== 3z ===
* E题没有仔细检查代码就提交连WA两发，是非常不值得的
=== hzf ===
* 码力和思维都不足，还是要多听取队友意见，适时打好辅助..同时平时多补题吧..
== 题解 ==
=== C - Robot ===
和NOIP的华容道比较类似，只有人在箱子旁边才能推动箱子，这样的状态才有意义。
所以，我们记状态(i,j,k)表示箱子在(i,j)，人在箱子第k个方向上的相邻格子。这样，我们只需要考虑给能互相转移的状态之间连边，在这张图上做一次bfs，就能知道哪些格子可以把箱子推过去了。
哪些状态可以互相转移呢？有两种情况：
1. 人往一个方向推了箱子。
2. 人不推箱子，从箱子的一边绕到了另一边。其实就是判断两个格子是否属于同一个双连通分量。
这道题挺难写的，写出来也爆栈，只能在本地测...现场赛有两支队伍通过，好厉害...
=== I - Cafebazaar ===
在做最大费用流时，如果某一条边必须流，可以把这条边的边权设为INF，然后答案里先扣掉INF，这样因为边权非常大，最大费用流肯定会先流这条边。
接下来就是比较明显的费用流构图了，从源点向每个员工连边，容量为1，如果是关键员工边权是INF，否则是0；每个员工向自己能开发的APP连边，容量为1，边权是开发能获得的受益；每个APP向汇点连边，容量为1，如果是关键APP边权是INF，否则是0.
注意这道题应该用最大费用流而不是最大费用最大流。最大费用最大流是在保证最大流的前提下做最大费用，不过费用流貌似有一个性质：每次得到的费用是不增的。这样，只要一次费用流的结果是非正的，我们就可以停止费用流了。
== 补题 ==
=== TsReaper ===
~~C~~, E, F, G
=== hzf ===
F, H, I| Run Id | Problem | Time | Status |
| 4 | A: Lobby | 12 | Yes |
| 12 | B: Cameras | 18 | No - WA |
| 15 | B: Cameras | 21 | Yes |
| 35 | F: Funfair | 36 | No - WA |
| 41 | F: Funfair | 44 | No - WA |
| 45 | F: Funfair | 56 | Yes |
| 50 | I: Cafebazaar | 67 | No - WA |
| 53 | H: DNA Sequencing | 78 | Yes |
| 69 | G: Beehive | 113 | No - WA |
| 72 | G: Beehive | 124 | Yes |
| 74 | I: Cafebazaar | 127 | Yes |
| 87 | J: Fence | 157 | Yes |
| 101 | E: Billboard | 211 | No - TLE |
| 118 | E: Billboard | 261 | Yes |
| 140 | C: Robot | 298 | No - TLE |
流水账
TsReaper
今天学长们会做的题最后都答对了，还是比较理想的。前期简单题A1y12，B题出现了一些失误，把1~9看成了0~9错了一次，B2y21。一段时间后hzf学长发现I题是比较经典的网络流，我就在Starve学长想F的时候上机先抄模板。Starve学长也很快想到了F的做法，改了两次错后F3y56。
不久后我的I题也写好了，但是并没有答对。我觉得模板和构图应该并没有错，只能自己先在一边debug，学长们讨论其它题的做法。学长们很快想到了H的做法，H1y78，继续思考G题。Starve学长想到把图放进一个坐标系里考虑，并猜出了一些结论。我认为这个结论可能并不正确，想让学长写稳一点的bfs幸好学长并没有听我的。Starve学长写题的过程中我和hzf学长debug I，学长发现我的做法是最大费用最大流，并不是最大费用流，背了一个锅...Starve学长G2y124后，我修改了一点代码，I2y127。学长们又发现J题是一个比较简单的凸包题，J1y157。
最后只剩下CDE三道题了，我们权衡之后觉得C和E可以尝试一下。我先想到了C题的一个做法，但是实现起来非常麻烦，不过学长们E题也还没有想好，我就先上机写。不久学长们想到了E题O(n3logn)的做法，手写了可删除的堆后E2y261，非常稳。最后40分钟我强行写了C，并没有答对。
3z
感觉今天发挥不错，虽然有一些代码失误，但是没有出现未知错误改不出来的情况。
hzf
今天学长们都好强...我又打了一发酱油...前期看到J，感觉像个凸包＋贪心，继续看I，像是个网络流二分图之类的，但是我不会处理下限...看H，感觉是个trie加个贪心什么的？但是我都没有具体的思路，tsr血行告诉我G可能比较好做，想叫我找个结论..然而我思路错了，推了一些复杂的公式，还是starve学长比较强...建立了正确的坐标系，猜到了正确的结论...过了这道题，期间我和tsr学长讨论了一下I，发现这道题不用保证流量最大，直接求费用最大即可，tsr学长很快找出了一个spfa最大流的性质：每次spfa得到的最长路不增，利用这个性质在spfa得到非正路径时结束算法即可...很强！
之后starve学长把J写了，很顺利。于是只剩下CDE，starve学长先叙述了一下E，并告诉我他的做法...我觉得很科学...但是不好维护。后来tsr学长和我看C，发现关键是怎么判断两个点在不经过某个点的情况下是否联通，实际上是个双连通分量...，学长希望在tarjan算法求割点的基础上做一些改动，但是很复杂...这时候starve学长E乱搞失败，下来换tsr学长写，不久Starve学长想出了E的正解：把尺取法对象换为行并用两个堆维护前k大数，复杂度比较科学了，正好tsr学长写不下去了...于是换starve学长继续写E，这段时间我和tsr学长又想了想C，但是编程复杂度还是比较高，还看了D，但是没有靠谱的做法...很快starve学长过了E，之后tsr学长一直写C直到结束...
总结
TsReaper
- 简单题还是WA了，很亏...
- 对网络流没有理解充分，混淆了最大费用流和最大费用最大流。大概需要网络流24题搞一波...？
3z
- E题没有仔细检查代码就提交连WA两发，是非常不值得的
hzf
- 码力和思维都不足，还是要多听取队友意见，适时打好辅助..同时平时多补题吧..
题解
C - Robot
和NOIP的华容道比较类似，只有人在箱子旁边才能推动箱子，这样的状态才有意义。
所以，我们记状态(i,j,k)表示箱子在(i,j)，人在箱子第k个方向上的相邻格子。这样，我们只需要考虑给能互相转移的状态之间连边，在这张图上做一次bfs，就能知道哪些格子可以把箱子推过去了。
哪些状态可以互相转移呢？有两种情况：
1. 人往一个方向推了箱子。
2. 人不推箱子，从箱子的一边绕到了另一边。其实就是判断两个格子是否属于同一个双连通分量。
这道题挺难写的，写出来也爆栈，只能在本地测...现场赛有两支队伍通过，好厉害...
I - Cafebazaar
在做最大费用流时，如果某一条边必须流，可以把这条边的边权设为INF，然后答案里先扣掉INF，这样因为边权非常大，最大费用流肯定会先流这条边。
接下来就是比较明显的费用流构图了，从源点向每个员工连边，容量为1，如果是关键员工边权是INF，否则是0；每个员工向自己能开发的APP连边，容量为1，边权是开发能获得的受益；每个APP向汇点连边，容量为1，如果是关键APP边权是INF，否则是0.
注意这道题应该用最大费用流而不是最大费用最大流。最大费用最大流是在保证最大流的前提下做最大费用，不过费用流貌似有一个性质：每次得到的费用是不增的。这样，只要一次费用流的结果是非正的，我们就可以停止费用流了。
补题
TsReaper
C, E, F, G
hzf
F, H, I
附加文件
- 2016-C02-team2.zip by TsReaper
- C.cpp by TsReaper