《管理信息化代码库.》由会员分享，可在线阅读，更多相关《管理信息化代码库.（121页珍藏版）》请在金锄头文库上搜索。
1、ACM/ICPC代码库 目录一数论31.阶乘最后非零位32. 模线性方程(组)33. 素数表34. 素数随机判定(miller_rabin)35. 质因数分解36. 最大公约数欧拉函数3二图论_匹配31. 二分图最大匹配(hungary邻接表形式)32. 二分图最大匹配(hungary邻接表形式,邻接阵接口)33. 二分图最大匹配(hungary邻接阵形式)34. 二分图最大匹配(hungary正向表形式)35. 二分图最佳匹配(kuhn_munkras邻接阵形式)36. 一般图匹配(邻接表形式)37. 一般图匹配(邻接表形式,邻接阵接口)38. 一般图匹配(邻接阵形式)39. 一般图匹配(正
2、向表形式)3三图论_生成树31. 最小生成树(kruskal邻接表形式)32. 最小生成树(kruskal正向表形式)33. 最小生成树(prim+binary_heap邻接表形式)34. 最小生成树(prim+binary_heap正向表形式)35. 最小生成树(prim+mapped_heap邻接表形式)36. 最小生成树(prim+mapped_heap正向表形式)37. 最小生成树(prim邻接阵形式)38. 最小树形图(邻接阵形式)3四图论_网络流31. 上下界最大流(邻接表形式)32. 上下界最大流(邻接阵形式)33. 上下界最小流(邻接表形式)34. 上下界最小流(邻接阵形式)3
3、5. 最大流(邻接表形式)36. 最大流(邻接表形式,邻接阵接口)37. 最大流(邻接阵形式)38. 最大流无流量(邻接阵形式)39. 最小费用最大流(邻接阵形式)3五. 图论_最短路径31. 最短路径(单源bellman_ford邻接阵形式)32. 最短路径(单源dijkstra_bfs邻接表形式)33. 最短路径(单源dijkstra_bfs正向表形式)34. 最短路径(单源dijkstra+binary_heap邻接表形式)35. 最短路径(单源dijkstra+binary_heap正向表形式)36. 最短路径(单源dijkstra+mapped_heap邻接表形式)37. 最短路径(
4、单源dijkstra+mapped_heap正向表形式)38. 最短路径(单源dijkstra邻接阵形式)39. 最短路径(多源floyd_warshall邻接阵形式)3六. 图论_连通性31. 无向图关键边(dfs邻接阵形式)32. 无向图关键点(dfs邻接阵形式)33. 无向图块(bfs邻接阵形式)34. 无向图连通分支(bfs邻接阵形式)35. 无向图连通分支(dfs邻接阵形式)36. 有向图强连通分支(bfs邻接阵形式)37. 有向图强连通分支(dfs邻接阵形式)38. 有向图最小点基(邻接阵形式)3七. 图论_应用31.欧拉回路(邻接阵形式)32. 前序表转化33. 树的优化算法34
5、. 拓扑排序(邻接阵形式).35. 最佳边割集36. 最佳顶点割集37. 最小边割集38. 最小顶点割集39. 最小路径覆盖3八. 图论_NP搜索31. 最大团(n小于64)(faster)32. 最大团3九. 组合31. 排列组合生成32. 生成gray码33. 置换(polya)34. 字典序全排列35. 字典序组合36. 组合公式3十. 数值计算31. 定积分计算(Romberg)32. 多项式求根(牛顿法)33. 周期性方程(追赶法)3十一. 几何31. 多边形32. 多边形切割33. 浮点函数34. 几何公式35. 面积36. 球面37. 三角形38. 三维几何39. 凸包(grah
6、am)310. 网格(pick)311. 圆312. 整数函数313. 注意3十二. 结构31. 并查集32. 并查集扩展(friend_enemy)33. 堆(binary)34. 堆(mapped)35. 矩形切割36. 线段树37. 线段树扩展38. 线段树应用39. 子段和310. 子阵和3十三. 其他31. 分数32. 矩阵33. 日期34. 线性方程组(gauss)35. 线性相关3十四. 应用31. joseph32. N皇后构造解33. 布尔母函数34. 第k元素35. 幻方构造36. 模式匹配(kmp)37. 逆序对数38. 字符串最小表示39. 最长公共单调子序列310.
7、最长子序列311. 最大子串匹配312. 最大子段和313. 最大子阵和3一数论1.阶乘最后非零位/求阶乘最后非零位,复杂度O(nlogn)/返回该位,n以字符串方式传入#include #define MAXN 10000int lastdigit(char* buf)const int mod20=1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2;int len=strlen(buf),aMAXN,i,c,ret=1;if (len=1)return modbuf0-0;for (i=0;i=0;i-)c=c*10+ai,ai=c/5,c%=5;return
8、ret+ret%2*5;2. 模线性方程(组)#ifdef WIN32typedef _int64 i64;#elsetypedef long long i64;#endif/扩展Euclid求解gcd(a,b)=ax+byint ext_gcd(int a,int b,int& x,int& y)int t,ret;if (!b)x=1,y=0;return a;ret=ext_gcd(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return ret;/计算ma, O(loga), 本身没什么用, 注意这个按位处理的方法 :-Pint exponent(int m,int a)
9、int ret=1;for (;a;a=1,m*=m)if (a&1)ret*=m;return ret;/计算幂取模ab mod n, O(logb)int modular_exponent(int a,int b,int n) /ab mod nint ret=1;for (;b;b=1,a=(int)(i64)a)*a%n)if (b&1)ret=(int)(i64)ret)*a%n;return ret;/求解模线性方程ax=b (mod n)/返回解的个数,解保存在sol中/要求n0,解的范围0.n-1int modular_linear(int a,int b,int n,int*
10、 sol)int d,e,x,y,i;d=ext_gcd(a,n,x,y);if (b%d)return 0;e=(x*(b/d)%n+n)%n;for (i=0;i0,wi与wj互质,解的范围1.n,n=w0*w1*.*wk-1int modular_linear_system(int b,int w,int k)int d,x,y,a=0,m,n=1,i;for (i=0;ik;i+)n*=wi;for (i=0;ik;i+)m=n/wi;d=ext_gcd(wi,m,x,y);a=(a+y*m*bi)%n;return (a+n)%n;3. 素数表/用素数表判定素数,先调用initpri
11、meint plist10000,pcount=0;int prime(int n)int i;if (n!=2&!(n%2)|(n!=3&!(n%3)|(n!=5&!(n%5)|(n!=7&!(n%7)return 0;for (i=0;plisti*plisti1;void initprime()int i;for (plistpcount+=2,i=3;i50000;i+)if (prime(i)plistpcount+=i;4. 素数随机判定(miller_rabin)/miller rabin/判断自然数n是否为素数/time越高失败概率越低,一般取10到50#include #if
12、def WIN32typedef _int64 i64;#elsetypedef long long i64;#endifint modular_exponent(int a,int b,int n) /ab mod nint ret;for (;b;b=1,a=(int)(i64)a)*a%n)if (b&1)ret=(int)(i64)ret)*a%n;return ret;/ Carmicheal number: 561,41041,825265,321197185int miller_rabin(int n,int time=10)if (n=1|(n!=2&!(n%2)|(n!=3&!(n%3)|(n!=5&!(n%5)|(n!=7&!(n%7)return 0;while (time-)if (modular_exponent(rand()&0x7fff16)+rand()&0x7fff+rand()&0x7fff)%(n-1)+1,n-1,n)!=1)return 0;return 1;5. 质因数
