给定一张有向图,边带权,保证图联通。
我们要想办法破坏他,破坏方式有两种。
1.选择一点i,使得进入它的所有边的边权之和每秒减少 xi (可以任意选择减少在哪条边上,也可以是几条边减少的权值之和)。
2.选择一点i,使得以它为起点的所有边的边权之和每秒减少 yi (可以任意选择减少在哪条边上,也可以是几条边减少的权值之和)。
当决定了一种方案后,伤害会同时产生,当这张图不连通时,即被破坏。
求使它破坏的最短时间。
联通的定义是,把它看成无向图后图联通。
(不确定是不是假题或者是NPC问题),求教qwq