Lucas's FireBox

MCMF经典题，将行列聚成点建图，由于计算的是连乘积，用取对数的方法把乘法变成加法作为流量建图计算 #include using namespace std; const int INF = 0x7fffffff; const int maxn = 1e5 + 50; const double INFF = 1.0 * 1e18; struct MEdge { int from, to, cap; double cost; MEdge(int from, int to, int cap, double cost) : from(from), to(to), cap(cap), cost(cost) {} }; struct MCMF

前言 你敢信你有生之年还会被树支配上几次？反正我是被支配了…… 支配树解决的是一个很现实的问题：假设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的最小值