非常困难
  • 板块学术版
  • 楼主JeffZhao
  • 当前回复22
  • 已保存回复22
  • 发布时间2023/1/17 21:29
  • 上次更新2023/10/24 03:47:39
查看原帖
非常困难
120017
JeffZhao楼主2023/1/17 21:29

征集本题做法。

有一张 2n2n 个点的二分图,左右部各 nn 个点,刚开始没有边。

现在要往二分图中加 mm 条边,每条边连接左部和右部各一个点。

对于二分图左部的一个点 ii,如果最终第 ii 个点的度数为 jj,那么就会付出 pi,jp_{i , j} 的代价,那么最终的代价就是所有点付出的代价之和。

求出使得二分图的最大匹配在 [l,r][l , r] 之间的最小代价。

n,m30n , m≤ 30

2023/1/17 21:29
加载中...