Lucas's FireBox

Thoughts, stories and ideas.

被树支配的恐惧

前言 你敢信你有生之年还会被树支配上几次?反正我是被支配了…… 支配树解决的是一个很现实的问题:假设S给T通过各种途径提供生(mo)命(fa)之源,但这些途径都有一个共性(都经过一个点),现在你想用最小的代价(摧毁尽可能少的点)抹除T,那么你应该摧毁哪些点 概念 给定一个有向图,给定起点S,终点T,在所有从S到T的路径中,如果删去某个点,则不存在一条路径能够使S到达T,则这个点被称为支配点。由支配点构成的树叫做支配树。支配树是一颗由起点S为根的树,根到树上任意一点路径经过的点都是它的支配点。 主要变量 dfn[x],表示dfs序 id[x], 表示dfs序对应的点 dfa[x], 第一遍dfs中,每个点的父节点 sdom[x], x的半支配点 idom[x], x的支配点 fa[x], 并查集(都懂) mindfn[x],从x到其已经被搜过的祖先的dfn的最小值
4 min read

Path - 2019 Multi-University Training Contest 1

题意 有一张n个点,m条边的有向图,切边的代价为边权,要求以最小的代价切掉一些边,使最短路变长 思路 先跑一遍Dijkstra,获得最短路,然后依照以下方法构造最短路图 if(dis[u[i]]+w[i] == dis[v[i]]){ addEdge(u[i],v[i],w[i]); } 其中dis[i]表示第1个点到第i个点的距离,u[i],v[i],w[i]分别为起点,终点,边权 之后就是求这张最短路图的最小割,根据最大流最小割定理,Dinic 跑一遍最大流即可 时间复杂度 O(玄学) Code //ItsLucas 2019.07.22
3 min read