板子们

板子们

数据结构 线段树 单点修改,区间和 ll tree[maxn << 2]; void build(int l, int r, int v) { memset(tree, v, sizeof(tree)); } void update(int root, int ... read more

Getting Confidence (MCMF)

MCMF经典题,将行列聚成点建图,由于计算的是连乘积,用取对数的方法把乘法变成加法作为流量建图计算 #include <bits/stdc++.h> using namespace std; const int INF = 0x7fffffff; const int maxn = 1e5 + 50; const double INFF = 1.0 * 1e18; ... read more

被树支配的恐惧

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