已注销

分类

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章（共1342篇）

有向图最小点基

ACM模版有向图最小点基参考：《有向图强连通分支》 /* * 有向图最小点基(邻接阵)O(n^2) * 点基B满足:对于任意一个顶点Vj,一定存在B中的一个Vi,使得Vi是Vj的前代。 * 返回点基大小和点基传入图的大小n和邻接阵mat,不相邻点边权0 需要调用强连通分支 * fin...

2021-05-22

0 333

Floyd求最小环

ACM模版 Floyd求最小环令e(u, v)表示u和v之间的连边，令min(u, v)表示删除u和v之间的连边之后u和v之间的最短路, 最小环则是min(u, v) + e(u, v). 时间复杂度是 O(EV^2). 改进算法在floyd的同时,顺便算出最小环 g[i][j]=i,...

2021-05-22

0 335

2-SAT

ACM模版 2-SAT /* * 2-sat 问题 * N个集团,每个集团2个人,现在要想选出尽量多的人, * 且每个集团只能选出一个人。如果两人有矛盾,他们不能同时被选中 * 问最多能选出多少人 */ const int MAXN = 3010; int n, m; int g[3010][3...

2021-05-22

0 398

二分图匹配相关

ACM模版二分图匹配匈牙利算法邻接矩阵+DFS /* * 初始化:g[][]两边顶点的划分情况 * 建立g[i][j]表示i->j的有向边就可以了,是左边向右边的匹配 * g没有边相连则初始化为0 * uN是匹配左边的顶点数,vN是匹配右边的顶点数 * 调用:res=hungar...

2021-05-22

0 650

无向图最小割

ACM模版无向图最小割 /* * INIT: 初始化邻接矩阵g[][] * CALL: res = mincut(n); * 注: Stoer-Wagner Minimum Cut; * 找边的最小集合，若其被删去则图变得不连通（我们把这种形式称为最小割问题） */ #define typec...

2021-05-22

0 702

最大流

ACM模版 Dinic算法 /* * Dinic 最大流 O(V^2 * E) * INIT: ne=2; head[]置为0; addedge()加入所有弧; * CALL: flow(n, s, t); */ #define typec int // type of cost...

2021-05-22

0 372

最小费用流

ACM模版 O(V * E * f) /* * 最小费用流 O(V * E * f) * INIT: network g; g.build(v, e); * CALL: g.mincost(s, t); flow=g.flow; cost=g.cost; * 注意: SPFA增广, 实际复杂度远...

2021-05-22

0 378

七月随笔

这个随笔，很短，很短，很短…… 和朋友谈起过往，我感悟道：一切的追求，在如愿以偿之前，都会带来无尽空虚与痛苦…… 而追求到后，不知道这个追求是否值得曾经那般！时常，这种既得的喜悦也很快会被冲淡啊…… …… 可是我依然会去不断追求，没有了追求，我还会剩些什么呢？朋友冷淡回应：我不会去追，我只...

2021-05-22

0 312

有上下界的流

ACM模版有上下界的最小（最大）流 /* * 有上下界的最小(最大)流 * INIT: up[][]为容量上界; low[][]为容量下界; * CALL: mf = limitflow(n,src,sink); flow[][]为流量分配; * 另附: 循环流问题 * 描述: 无源无汇的网络...

2021-05-22

0 414

最佳边割集

ACM模版最佳边割集 #define MAXN 100 #define inf 1000000000 int max_flow(int n, int mat[][MAXN], int source, int sink) { int v[MAXN], c[MAXN], p[MAXN], ...

2021-05-22

0 362