2017-Sp40-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，cjb觉得A很可做，就和yzc讨论了起来，期间看到G和J都有人过了，cjb读G，yzc读J，yzc随后上机写J，'''J1y17'''. cjb紧接着上机写G，'''G1y26'''. yzc在cjb写G的时候想好了A的细节，随后上机写A，'''A1y44'''. sub表示做出了K，上机写K，'''K1y53'''，并获得了一血。cjb和yzc觉得D是个比较简单的dp，yzc上机写，很快写完了，获得wa。此时发现很多队伍过了C，cjb读了C，和sub讲了讲，三个人讨论了一下。cjb之后构造出了dp错误的样例，发现其实是不能dp的，估计只能最小割，cjb想了想建图就上机写D，不久后'''D1y102'''. yzc和sub完善了C的细节，D过了之后yzc上机写C，'''C1y114'''. 接下来sub上机写I，yzc开B的大模拟题，cjb开H的点分治题，sub wa了一发后发现构造不符合条件，下机思考，yzc上机写B。一段时间后sub重新上机写I，之后'''I2y170'''. yzc感觉B写不完就放弃了，剩下时间sub一个人做E，打了暴力，各种搞式子找规律，最后'''E1y264'''，抢下了一血. 在现场rk3，次于8题的SJTU_Dreadnought和THU_Tear Bear.
== 总结 ==
=== chenjb ===
sub好强....这个E我好佩服QAQ 希望在去北京前能总结下网络流模型啊....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * D：把获得技能u的任一方式，表为从源点到点u的一个割。从这个方向思考的话，便可以得到以下的建图策略：
   * 将每个点i，拆成i和i'，另外添加一个源点source，以及汇点sink；
   * 对于原来DAG中的边，u->v，连边u'->v，容量为DAG中对应边的费用；  
   * 对于每个点u，连边source->u，容量为P[u]；连边u->u'，容量为D[u]；
   * 对于目标技能s，连边s'->sink，流量INF；
   * 然后答案就是source->sink的最小割。
 * [https://wiki.icpc-camp.org/dreadnought/2015%20ACM-ICPC%20Asia%20Regional%20Beijing Dreadnought]
== 补题 ==

流水账

开场各自看题，cjb觉得A很可做，就和yzc讨论了起来，期间看到G和J都有人过了，cjb读G，yzc读J，yzc随后上机写J，J1y17. cjb紧接着上机写G，G1y26. yzc在cjb写G的时候想好了A的细节，随后上机写A，A1y44. sub表示做出了K，上机写K，K1y53，并获得了一血。cjb和yzc觉得D是个比较简单的dp，yzc上机写，很快写完了，获得wa。此时发现很多队伍过了C，cjb读了C，和sub讲了讲，三个人讨论了一下。cjb之后构造出了dp错误的样例，发现其实是不能dp的，估计只能最小割，cjb想了想建图就上机写D，不久后D1y102. yzc和sub完善了C的细节，D过了之后yzc上机写C，C1y114. 接下来sub上机写I，yzc开B的大模拟题，cjb开H的点分治题，sub wa了一发后发现构造不符合条件，下机思考，yzc上机写B。一段时间后sub重新上机写I，之后I2y170. yzc感觉B写不完就放弃了，剩下时间sub一个人做E，打了暴力，各种搞式子找规律，最后E1y264，抢下了一血. 在现场rk3，次于8题的SJTU_Dreadnought和THU_Tear Bear.

总结

chenjb

sub好强....这个E我好佩服QAQ 希望在去北京前能总结下网络流模型啊....

oipotato

subconscious

题解

D：把获得技能u的任一方式，表为从源点到点u的一个割。从这个方向思考的话，便可以得到以下的建图策略：
- 将每个点i，拆成i和i'，另外添加一个源点source，以及汇点sink；
- 对于原来DAG中的边，u->v，连边u'->v，容量为DAG中对应边的费用；
- 对于每个点u，连边source->u，容量为P[u]；连边u->u'，容量为D[u]；
- 对于目标技能s，连边s'->sink，流量INF；
- 然后答案就是source->sink的最小割。
Dreadnought

补题

附加文件

1.png by chenjb