题意:n个点m条边的有向图求1~n最小割 但是要求1~n之间的路径不能不经过割边(显然) 且1~n的路径中不能有任何一条经过两条以上的割边

那么考虑一个割割开之后分成s,t集合那么如果会产生这种问题一定是集合t有连回s的边 那么会重复转圈走所以给每条边都添加inf的边 让这样的问题消失 然后跑最大流即可 不存在的话输出-1即可 注意存在反例即 原本不在1,n路径上的点是不可以添加这样的inf边的

 

分类: 最大流最小割

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论