被树支配的恐惧

前言你敢信你有生之年还会被树支配上几次?反正我是被支配了……支配树解决的是一个很现实的问题:假设S给T通过各种途径提供生(mo)命(fa)之源,但这些途径都有一个共性(都经过一个点),现在你想用最小的代价(摧毁尽可能少的点)抹除T,那么你应该摧毁哪些点概念给定一个有向图,给定起点S,终点T,在所有从S到T的路径中,如果删去某个点,则不存在一条路径能够使S到达T,则这个点被称为支配点。 ...

Path - 2019 Multi-University Training Contest 1

题意有一张n个点,m条边的有向图,切边的代价为边权,要求以最小的代价切掉一些边,使最短路变长思路先跑一遍Dijkstra,获得最短路,然后依照以下方法构造最短路图if(dis[u[i]]+w[i] == dis[v[i]]){ addEdge(u[i],v[i] ...