应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N

来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/27 13:00:52
应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N是最大流.一万多个点是可以搞定的

应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N
应该是二分图匹配吧
左边和右边两个子图
左边的图有N个点(N

应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N
是最大流.
一万多个点是可以搞定的
建图如下
源点到左边的点都连上一条边,容量为w[i]
右边的点都向汇点边一条边,容量为1
然后左边和右边的点有边的都边上容量为1的边,方向是从左边点到右边点.
然后最大流,最大流的值就是答案.