【W的AC计划 - 第九期】网络流

发布时间 2023-09-01 21:06:04作者: hh2048

题单

P1344:最小割

由两问构成,第一问直接运行最小割即可,第二问比较困难,容易想到建议另一个边权均为 \(1\) 的网络然后再跑一遍最小割,然而这样是错误的:新图的答案并不对应给定图的最小割,hack数据见此

所以这里采用一个智慧的数学技巧:将给定边权扩大后用末尾位记录第二问的答案,能同时跑出两个问的答案,分离后输出即可。