青烟绕指柔

分类

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章（共382篇）

dijkstra + 势函数费用流

dijkstra因为不能处理负权最短路，所以不能用来费用流的增广。但是如果我们利用Johnson的思想，加一个势函数，把负变正，就能跑费用流了。维护势函数也很简单，每次跑完dijkstra之后，对于最短路非INF的点，令势函数加上最短路即可。 dijkstra跑增广时直接把 w[i] -&...

2019-12-27

0 534

多边形重心

例题：hdu 1115 给出一堆点，求多边形的重心。我们可以把多边形划分为许多三角形。三角形的重心很简单： x = ( x1 + x2 + x3 ) / 3 , y = ( y1 + y2 + y3 ) / 3 多边形的重心公式为：借用大佬博客的图片：https://blog.cs...

2019-12-27

0 610

自适应Simpson

Simpson是什么呢？就是如果我们要求一个积分，但是里面的f(x)十分麻烦，于是我们就需要用Simpson的抛物线来近似最后的答案。加一个自适应就是适应精度，当精度很小的时候，就直接返回。 Simpson公式：例题：Simpson例题 AC代码： #pragma GCC ...

2019-12-27

0 586

三角剖分与泰森多边形

泰森多边形：大概就是一个平面划分，平面上的每个点划分到离它最近的关键点上。 Delaunay三角剖分和泰森多边形是对偶图。 Delaunay三角剖分：定理：对于任何一种三角剖分，三角形个数和外围凸包点数之和为2n-2。 Delaunay三角剖分的性质 1.平面上的点集有且仅有唯一的Del...

2019-12-27

0 679

[USACO4.4]追查坏牛奶

题目描述你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车...

2019-12-27

0 493

Codeforces Biologist

题目链接：CF311E Biologist 最小割（最大权闭合子图）。对于每个点有两个状态，而不是以往最大权闭合子图的一个状态。所以我们要对于0,1的点判断一下。如果点为0，那么S连向此点，表示此点变为1的代价。如果点为1，那么此点连向T，表示此点变为0的代价。那么对于我们的需求...

2019-12-27

0 393

Codeforces - E. Tourism

E. Tourism time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Alex decided to go on a touristi...

2019-12-27

0 453

带树开花 - 带花树

带花树主要用来找一般图的最大匹配。例题：带花树例题如果是二分图，我们可以很简单的用匈牙利或者网络流等等方法找出来最大匹配。但是如果不是二分图呢？（有奇环）我们就需要用到带花树了。主要步骤：首先，奇环中有2k+1个点，所以最多有k组匹配。这就是说，有一个点没有匹配，即这个点...

2019-12-27

0 380

K Subsequence

K Subsequence Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3577 Accepted Submission(s): 898 ...

2019-12-27

0 420

Codeforces - Beautiful Mirrors

E. Beautiful Mirrors time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Creatnx has n mirrors...

2019-12-27

0 566