Lucas

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的最小值

题目 Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try

题目 Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city ui to vi (and vise versa) using the i-th road,

题意 有一张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