BZOJ2039 employee人员雇佣 && BZOJ2127 happiness  最小割模型 图论

BZOJ2039 employee人员雇佣 && BZOJ2127 happiness 最小割模型

这俩题是最小割的经典模型,即获得一个点的价值后还可能获得其与其他点的“绑定价值”。对于这样的题,可以先考虑仅有一个“限制关系”,即仅有一个获利规则,然后在此基础上继续添加限制条件。利用最小割,可以将“获得利益”转化为“舍弃最小利益”,然后用总获利减去舍弃的,即为获得的最大利益。在构图时,可以先搞个简···
网络流模版 图论

网络流模版

最大流问题:Dinic [crayon-5a5f4f02d5d6e249222375/] 最小费用最大流 [crayon-5a5f4f02d5d77413394569/] 还有一个写的好看一些的: [crayon-5a5f4f02d5d7b127670934/]