COGS的这一题是超级满配版本

比洛谷的要强力的多：894. 追查坏牛奶 - COGS

额外要求是：求出最小割流量，同时求出割边最小，同时字典序最小的方案

输出割掉的边

最小割流量好求，最小割边的数量也好求，但同时确定哪条边不太好弄，因为存在方法互斥

首先：最小割流量就是跑最大流的结果

求最小割边的数量，需要在刚刚跑完最大流的网络上

把所有的满流边流量重新标记为1，不满流的重新标记为INF

在新的网络上跑一次最大流

这个时候得到的流量就是最小割边的数量

正确性：

满流边一定是某条流量通路的瓶颈路(虽然不一定是唯一瓶颈路)

把满流的边标记成1去跑增广路

得到的结果就是没有公共边的流量通路的条数(因为公共边只允许通过1点流量被计算一次)

那么就给这这些流量通路每个断开一条边即可(如果存在公共边先断开公共边)

如何求最小字典序的方案：

在最小割的情况下

首先要记住，我们一定是优先断开边权最大的必须满流边(删去这条边后，重新对整个网络跑最大流，最大流量会减小这个边的边权那么多(也就是这条边的传递作用无可替代))

那么找最小字典序方案也出来了：在正常的图上，先跑一次最大流

然后枚举所有边（首先把边按照边权(大到小)-字典序(小到大)两个关键字排序）

先复原整个网络到未增广形态

然后尝试删去这条边，看最大流结果减少的是否是这条边流量那么多

如果是，说明这是关键边，记录这条边会被删除(贪心保证了删除的边数目最少，因为这条边满流，不删它就要删和它在同一支流的多条边) 把这条边永久性删除，并将最大流的结果减小(该边的流量)那么多

这就导致你需要先用正常的边权跑DINIC，再用1和INF的边权跑DINIC，再用正常的边权去找应当被删除的边