已注销

ACM模版篇

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)

/ 注册

全部文章 / ACM模版篇（共139篇）

输入输出外挂总结

题外话明明在C语言中有scanf()、printf()，C++中有cin、cout，为什么我们还要用输入输出外挂呢？这个问题很明显，一定是因为这些输入输出函数功能过于强大而导致效率低，（很多时候，功能越强大的东西越臃肿），而我们使用的输入输出外挂既然叫外挂，那说明其一定有很大的优势，而这方面...

2021-05-22

0 535

最短路

ACM模版 Dijkstra 单源最短路邻接矩阵形式 /* * 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2) * 求出源beg到所有点的最短路径，传入图的顶点数和邻接矩阵cost[][] * 返回各点的最短路径lowcost[]，路径pre[]，pre[i]记录beg...

2021-05-22

0 385

第K短路

ACM模版 Dijkstra /* * Dijkstra变形，可以证明每个点经过的次数为小于等于K， * 所有Dijkstra的数组dist由一维变为二维，记录经过该点 * 1次、2次......k次的最小值 * 输出dist[n - 1][k]即可 */ int g[1010][1010];...

2021-05-22

0 348

最小生成树（森林）

ACM模版 Prim算法 /* * Prim求MST * 耗费矩阵cost[][]，初始化为INF，标号从0开始，0 ~ n－1 * 返回最小生成树的权值，返回-1表示原图不连通 */ const int INF = 0x3f3f3f3f; const int MAXN = 110; bool...

2021-05-22

0 952

次小生成树

ACM模版 O(V^2) 结论次小生成树可由最小生成树转换一条边得到证明 T是某一棵最小生成树，T0是任一棵异于T的树，通过变换T0->T1->T2->…->Tn(T)变成最小生成树，所谓的变换是，每次把T_i中的某条边换成T中的一条边，而且树T_(i + 1)...

2021-05-22

0 465

POJ－3241－Object Clustering

ACM模版曼哈顿最小生成树 POJ 3241 Object Clustering 曼哈顿距离简单说，他指两点之间的横纵坐标的差的绝对值之和。题意查找平面上的点的曼哈顿距离最小生成树的第n－k小边的长度，点数在100000以内。解析对于曼哈顿距离...

2021-05-22

0 658

欧拉路径

ACM模版欧拉回路每条边只经过一次，而且回到起点无向图：连通（不考虑度为0的点），每个顶点度数都为偶数。 /* * SGU 101 */ struct Edge { int to; int next; int index; int dir; ...

2021-05-22

0 496

DAG的深度优先搜索标记

ACM模版 DAG && DFS /* * DAG(有向无环图)的深度优先搜索标记 * INIT:edge[][]邻接矩阵；pre[], post[], tag全置0 * CALL:dfsTag(i, n); pre/post:开始/结束时间 */ const int V = ...

2021-05-22

0 520

图的割点、桥和双连通分支的基本概念

ACM模版点连通度与边连通度在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。一个图的点连通度的定义为,最小割点集合中的顶点数。类似的,如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这...

2021-05-22

0 673

无向图连通度（割）

ACM模版无向图连通度（割） /* * INIT: edge[][]邻接矩阵；vis[],pre[],anc[],deg[]置为0； * CALL: dfs(0, -1, 1, n); * k = deg[0], deg[i] + 1(i = 1...n - 1)为删除该节点后得到的连通图个数...

2021-05-22

0 432