已注销
已注销
全部文章
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
533
最短路
ACM模版 Dijkstra 单源最短路 邻接矩阵形式 /* * 单源最短路径,Dijkstra算法,邻接矩阵形式,复杂度为O(n^2) * 求出源beg到所有点的最短路径,传入图的顶点数和邻接矩阵cost[][] * 返回各点的最短路径lowcost[],路径pre[],pre[i]记录beg...
2021-05-22
0
384
第K短路
ACM模版 Dijkstra /* * Dijkstra变形,可以证明每个点经过的次数为小于等于K, * 所有Dijkstra的数组dist由一维变为二维,记录经过该点 * 1次、2次......k次的最小值 * 输出dist[n - 1][k]即可 */ int g[1010][1010];...
2021-05-22
0
347
最小生成树(森林)
ACM模版 Prim算法 /* * Prim求MST * 耗费矩阵cost[][],初始化为INF,标号从0开始,0 ~ n-1 * 返回最小生成树的权值,返回-1表示原图不连通 */ const int INF = 0x3f3f3f3f; const int MAXN = 110; bool...
2021-05-22
0
950
次小生成树
ACM模版 O(V^2) 结论 次小生成树可由最小生成树转换一条边得到 证明 T是某一棵最小生成树,T0是任一棵异于T的树,通过变换T0->T1->T2->…->Tn(T)变成最小生成树,所谓的变换是,每次把T_i中的某条边换成T中的一条边,而且树T_(i + 1)...
2021-05-22
0
462
POJ-3241-Object Clustering
ACM模版 曼哈顿最小生成树 POJ 3241 Object Clustering 曼哈顿距离 简单说,他指两点之间的横纵坐标的差的绝对值之和。 题意 查找平面上的点的曼哈顿距离最小生成树的第n-k小边的长度,点数在100000以内。 解析 对于曼哈顿距离...
2021-05-22
0
655
欧拉路径
ACM模版 欧拉回路 每条边只经过一次,而且回到起点 无向图: 连通(不考虑度为0的点),每个顶点度数都为偶数。 /* * SGU 101 */ struct Edge { int to; int next; int index; int dir; ...
2021-05-22
0
495
DAG的深度优先搜索标记
ACM模版 DAG && DFS /* * DAG(有向无环图)的深度优先搜索标记 * INIT:edge[][]邻接矩阵;pre[], post[], tag全置0 * CALL:dfsTag(i, n); pre/post:开始/结束时间 */ const int V = ...
2021-05-22
0
518
图的割点、桥和双连通分支的基本概念
ACM模版 点连通度与边连通度 在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。一个图的点连通度的定义为,最小割点集合中的顶点数。 类似的,如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这...
2021-05-22
0
666
无向图连通度(割)
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
431
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页