先写个暴力练手dinic回头再补qwq

用手寫隊列在bzoj上RE了。。。
STL大法好！！！

为什么我网络流0.191s就过了啊....

强行最大流卡时A
改成最短路后，感觉代码整齐些是好的。。
BZOJ上不断挑战数组大小，在RE和M的边界上挣扎了8次才过。。

以撒在这边可过,隔壁BZOJ炸内存

BZOJ上内存是162MB

为什么spfa都过了。。。
一开始是超时的。。后来我想“特判”（dabiao)一下，结果就过了。。。

膜拜最大流完爆的常数帝......

对偶图是什么鬼，可以吃吗？
红果果的最大流，常数大如狗......只好特判了，罪过，罪过

回复 @Asm.Def :
是数据弱不是我算法好。。
神犇又在D我

回复 @HouJikan :
QAQ给常数帝跪了。。居然直接最大流就能过QAQ

数据好弱啊。。我在BZOJ上RE的代码在这里可以AC。。
我还是用的裸最大流。。
什么对偶图完全看不懂

神奇的对偶图……图论告诉我们，对于平面图，原图的“路径”和对偶图的“割”一一对应= = 所以可以直接套最短路……（我没有考虑图本身的特点，奢侈地用邻接表存了图……）

这题在BZOJ上的数据跟这里的不一样（应该是这里的数据少了几组）
在BZOJ上N或M可能为1，这点非常*******，记得交到BZOJ上要特殊判断。

郁闷，为啥会超时一组～

我用陳立杰的代碼來測試測試數據。淡定淡定
解決超時： 在Dijkstra擴展時，加一下：if(u==Sink) {printf("%d",-PQ.top().first);return;}