已注销

分类

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篇）

Minimal Steiner Tree（MST）

ACM模版 MST /* * Minimal Steiner Tree * G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树. * 时间复杂度:O(N^3+N*2^A*(2^A+N)) * INIT: d[][]距离矩阵; id[]置为集合A中点的标号; * CALL: st...

2021-05-22

0 439

有向图的强连通分量

ACM模版 Tarjan /* * Tarjan算法 * 复杂度O(N+M) */ const int MAXN = 20010; // 点数 const int MAXM = 50010; // 边数 struct Edge { int to, next; }edge[MAXM]; ...

2021-05-22

0 362

双连通分支

ACM模版点双连通分支去掉桥,其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话,把双连通子图收缩为一个点,形成一颗树。需要加的边为(leaf+1)/2 (leaf 为叶子结点个数) 参考题目链接： POJ 3177 Redundant Paths 给定一个连通的...

2021-05-22

0 329

Tarjan强连通分量

ACM模版 Tarjan强连通分量 /* * Tarjan 强连通分量 * INIT: vec[]为邻接表; stop, cnt, scnt置0; pre[]置-1; * CALL: for(i=0;i<n;++i)if(-1==pre[i])tarjan(i,n); */ const i...

2021-05-22

0 436

弦图判断

ACM模版弦图判断 /* * 弦图判断 * INIT: g[][]置为邻接矩阵; * CALL: mcs(n); peo(n); * 第一步: 给节点编号 mcs(n) * 设已编号的节点集合为A, 未编号的节点集合为B * 开始时A为空, B包含所有节点. * for num=n-1 dow...

2021-05-22

0 421

弦图的PERFECT ELIMINATION点排列

ACM模版弦图的PERFECT ELIMINATION点排列 /* * INIT: g[][]置为邻接矩阵; * CALL: cardinality(n);tag[i]为排列中第i个点的标号; */ const int V = 10010; int tag[V], g[V][V],...

2021-05-22

0 322

稳定婚姻问题

ACM模版稳定婚姻问题 /* * 稳定婚姻问题O(n^2) */ const int N = 1001; struct People { bool state; int opp, tag; int list[N]; // man使用 int pri...

2021-05-22

0 514

拓扑排序

ACM模版拓扑排序 /* * 拓扑排序 * INIT:edge[][]置为图的邻接矩阵;cnt[0...i...n-1]:顶点i的入度。 */ const int MAXV = 1010; int edge[MAXV][MAXV]; int cnt[MAXV]; void TopoOrde...

2021-05-22

0 456

无向图连通分支

ACM模版无向图连通分支 /* * 无向图连通分支(dfs/bfs邻接阵) * DFS / BFS / 并查集 * 返回分支数,id返回1.分支数的值 * 传入图的大小n和邻接阵mat,不相邻点边权0 */ #define MAXN 100 void search(int ...

2021-05-22

0 360

有向图强连通分支

ACM模版有向图强连通分支 /* * 有向图强连通分支(dfs/bfs邻接阵)O(n^2) * 返回分支数,id返回1..分支数的值 * 传入图的大小n和邻接阵mat,不相邻点边权0 */ #define MAXN 100 int find_components(int n, int mat[...

2021-05-22

0 374