请教一下大佬
  • 板块学术版
  • 楼主Lindone
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/16 10:22
  • 上次更新2024/9/16 13:46:15
查看原帖
请教一下大佬
679239
Lindone楼主2024/9/16 10:22

给定一个含有n个节点m条边的有向图,第i条边的权重为w[i],定义图的超级源点u为:从u出发,可以到达图中的任何节点。但是给定的图中有可能不含有超级源点,所以你可能需要反转图中的一些边的方向,使得图中出现超级源点,反转的代价为所需要反转的边中的权值的最大值。图中保证不含有重边和自环。问你需要付出的代价最小值是多少,如果不存在答案,输出-1。

这道题我是用二分答案做的,我每次将小于mid的边都会建一个反向边,然后tarjan缩点,最后判断源点个数是否为1,请问这样的思路有没有问题

2024/9/16 10:22
加载中...