回复 @noip :
看题要看完

没有spj怎么输出任意一个？

不得不承认，被这题虐爆了...ORZ ZZX

如果用的是DINIC,统计答案的时候只要判断该节点标记是否大于等于0就可以判断是否要输出了

回复 @digital-T :
orz

回复 @Gold Miner : +10086

1A的感觉真好啊……（谜の音：明明是对着标程写的……）
绳命中第一道splay，

@cstdio :
亲爱的cstdio：
你好，我是郑州一中NOIP的丁泽方。在COGS上的UID=2059。希望将我们分到COGS上的郑州一中分组中。
以下是郑州一中NOIP新人的名单：
用户名称------------UID
丁泽方--------------2059
第三十八年夏至-------2057
我叫方旭------------2058
幻灵子--------------2035
麻烦了。
因为联系不到你，所以我只好在这里回复你了，若有不妥之处，望谅解。
丁泽方
2014.3.10

真水

回复 @King_Algorithm :
喂喂不要乱封线段树导师啦……我被神犇们solo了怎么办？再说还不是你信手拈来，现在敲线段树比我溜多了= =

好长时间后……和我说我时间超限了…………

用堆优化的迪杰斯特拉写的。。
对任意2节点求单元最短路。把结果存到系统红黑树map里(这样保证内存不会爆)。
然后对应每条询问输出结果即可。
但是为何伤心的T了7组

我对题目已经无语了QAQ^^^苗苗苗

好多DP都是可以用线段树写的。
一种简单容易看出的DP(可以直接以区间建树)有以下特点：
1.子问题数量少(太多的话会把一个节点建的巨复杂)(这种情况下还是交给cstdio大神来建一些高大上的树)
甚至可以写成O(n)的地推。子问题处理到该问题的状态转移更一般形式的方程就是子节点计算父节点的运算法则。
2.相关子问题不要调用相邻很远的节点的值，譬如石子归并。不过话说区间DP还是可以套线段树的。要不然再套一颗建立与其他节点之间的联系。要不按照子问题建树而非区间。(这是的时间复杂度就不是以区间长度为准的了)
更多的研究还有待寡人继续学习,或咨询@cstdio 和线段树导师@digital-T
不过也不至于又让我用32min的单指敲键盘敲得内存和时间压制你们吧

回复 @高高高高高 :
哇，比我快我的怎么算正解。。。。。。
我是记录所有点到所有枢纽的最短路 和 所有枢纽到所有点的最短路 判断时枚举枢纽 即可
内存……时间……都非常拙计啊

回复 @digital-T :
这题正解是什么？

回复 @cstdio :
太神了，目测省选要被你们虐了

居然要用到高精度......

回复 @Chenyao :
每次12个数取4个怎么大了……

回复 @cstdio :
觉得常数有些可怕