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

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/19 15:41:49
应该是二分图匹配吧左边和右边两个子图左边的图有N个点(N
xJ@_$xy@7/5jbf-E$B!mAh"֗$'_lů?3k96^m*xܭ d% n# AA`JTM6j?ob"2hZ_Po:OS#N]H&ب"ĺ JE6dAzڌ+B8j!>˓m h~XG޶FU3 @G]-m@\!:U0yÔ ^2[3֣knj $O

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

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