为什么我用链表还是超时啊？？？？？？？？

原来网上的DINIC标程骗人的 效率巨低

还是根据自己的理解编就对了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 446ms

├ 测试数据 10：答案正确... 493ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：939ms

朴素的Dinic

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

sap+gap+当前弧

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 368ms

├ 测试数据 10：答案正确... 368ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：736ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 119ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：207ms

囧 感谢sfz97308提供数据规模...

Distance Label Shortest Path

你用

#include "dos.h"

下的

system("color ");

就可以了

在那个位置就是写上两个16进制的数

比如说color 1a

color c5

你可以参考一下那个cmd里面的color help命令

郁闷要死。。

朴素Dinic总是超，加了贪心初始流也超，郁闷。。。

研究SAP去。。。。。

编译通过...

帮发题人把范围补上：

【数据规模和约定】

80%的数据中：N≤200，M≤1 000。

100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

太无语啦...不会...

这道题最后两个点太WS了。

我的做法SAP+GAP+当前弧才AC。

建图是这样的，S与所有客户群连，边权为价值，客户群与中转站连接，边权为+00，中转站与T连接，边权为建造费。

接下来就是求最小割了。。

最后2个点死超..据某大犇说他写的Dinic都超..我就邪恶地cheat了..

niunuiu=uasrqwe

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 197ms

├ 测试数据 10：答案正确... 212ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：409ms

搞通dinic

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：82ms

随便写个SAP就这样了

最后2个点好大。。。

不想再重新写所以cheat了。。

地心有了没？？？？？？？

-_-|||

还没人打过这样的颜色...

........晕~怎么把字弄成彩色的啊？

vvvvvvvvvv

这题很有难度

有兴趣的可以查看NOI2006的解题报告或今年WC论文……

Dinic应该算一种方法，还有贪心初始流？忘了……

神阿，来讲解一下！！！！！！！！！！！！！！！！