刚学网络流,自己乱胡了一道题,还没想出做法
  • 板块灌水区
  • 楼主Lagerent
  • 当前回复20
  • 已保存回复20
  • 发布时间2023/3/11 08:54
  • 上次更新2023/10/23 21:58:34
查看原帖
刚学网络流,自己乱胡了一道题,还没想出做法
477674
Lagerent楼主2023/3/11 08:54

给定一张有向图,边带权,保证图联通。

我们要想办法破坏他,破坏方式有两种。

1.选择一点ii,使得进入它的所有边的边权之和每秒减少 xix_i (可以任意选择减少在哪条边上,也可以是几条边减少的权值之和)。

2.选择一点i,使得以它为起点的所有边的边权之和每秒减少 yiy_i (可以任意选择减少在哪条边上,也可以是几条边减少的权值之和)。

当决定了一种方案后,伤害会同时产生,当这张图不连通时,即被破坏。

求使它破坏的最短时间。

联通的定义是,把它看成无向图后图联通。

(不确定是不是假题或者是NPC问题),求教qwq

2023/3/11 08:54
加载中...