求助最长路
  • 板块学术版
  • 楼主TankYu
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/20 09:42
  • 上次更新2023/11/2 12:37:56
查看原帖
求助最长路
408071
TankYu楼主2023/10/20 09:42

RT,路径的定义为点权和加边权和,其中 不允许重复经过同一个点和边

求最长路

口胡的做法:把点拆成2个,流量1,费用是点权取反,边是流量1,费用边权取反,然后虚拟源连每个点流量inf,费用0,每个点的新建拆点连虚拟汇,流量inf费用0,然后跑最小费用最大流

能不能更优

2023/10/20 09:42
加载中...