ACM常用算法模板
专用模板目录：一、图论1 最大团2 拓扑排序3 最短路和次短路4 SAP模板5 已知各点度，问能否组成一个简单图6 KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学 1. 剩余定理 2. N!中质因子P的个数 3.拓展欧几里得 4.三角形的各中心到顶点的距离和 5.三角形外接圆半径周长 6.归并排序求逆序数 7. 求N！的位数 8.欧拉函数 9. Miller-Rabin,大整数分解，求欧拉函数 10. 第一类斯特林数 11.计算表达式 12.约瑟夫问题 13高斯消元法 14. Baby-step,giant-step n是素数.n任意 15. ab%c=a (b%eular(c)+eular(c) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20. 行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构 1树状数组 2.线段树求区间的最大、小值 3.线段树求区间和 4.单调队列 5.KMP模板 6. 划分树，求区间第k小数 7.最大堆，最小堆模板 8. RMQ模板求区间最大、最小值 9.快速排序，归并排序求逆序数. 10.拓展KMP 四、计算几何1. 凸包 面积2. Pick公式 求三角形内部有多少点 3. 多边形边上 内部各多少点以及面积 pick4. 平面最远点对5. 判断矩形是否在矩形内6. 判断点是否在多边形内7. 判断4个点(三维)是否共面8. 凸包 周长9. 等周定理变形 一直两端点和周长 求最大面积10. 平面最近点对11. 单位圆最多覆盖多少点(包括边上)12. 多边形费马点 求点到多边形各个点的最短距离13. 矩形并周长14. zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;/当前顶点数int best;/当前最大顶点数int vis50;/当前解int bestn50;/最优解int map5050;/临界表void dfs(int i) if(i>n) for(int j=1;j<=n;j+) bestnj=visj; best=cn; return ; int ok=1; for(int j=1;j<i;j+) if(visj=1&&mapij=0) ok=0; break; if(ok) /进入左子树 visi=1; cn+; dfs(i+1); cn-; if(cn+n-i>best) /进入右子树 visi=0; dfs(i+1); int main() while(scanf("%d%d",&n,&m)=2) memset(vis,0,sizeof(vis); memset(map,0,sizeof(map); while(m-) int p,q; scanf("%d%d",&p,&q); mappq=mapqp=1;/无向图 cn=0; best=0; dfs(1); printf("%dn",best); return 0;2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map105105,in105,vis105,ans105,n;int flag;void dfs(int step) if(flag) return ;if(step=n+1) flag=1; printf("%d",ans1);for(int i=2;i<=n;i+) printf(" %d",ansi);printf("n");return ; for(int i=1;i<=n;i+) if(visi=0&&ini=0) visi=1; for(int j=1;j<=n;j+) if(mapij>0) mapij=-mapij; inj-; ansstep=i; dfs(step+1); visi=0; for(int j=1;j<=n;j+) if(mapij<0) mapij=-mapij; inj+; int main() while(scanf("%d",&n)=1) flag=0; memset(map,0,sizeof(map); memset(vis,0,sizeof(vis); memset(in,0,sizeof(in); for(int i=1;i<=n;i+) int t; while(scanf("%d",&t),t) mapit=1; int+; dfs(1); return 0; 3最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node public: int e,w;/表示终点和边权; const int inf=(1<<25); int main() int ci; cin>>ci; while(ci-) vector<Node> G1005;/用邻接表存边 int n,m; cin>>n>>m; for(int i=1;i<=m;i+) Node q;int u; cin>>u>>q.e>>q.w; Gu.push_back(q); int s,f;/起点和终点 cin>>s>>f; /dijkstra 求最短路和次短路 int flag10052; int dis10052,cnt10052;/0表示最短路，1表示次短路 memset(flag,0,sizeof(flag); for(int i=1;i<=n;i+) disi0=disi1=inf; diss0=0;cnts0=1;/初始化 for(int c=0;c<2*n;c+) /找最短路和次短路，故要进行2*n次循环也可以改成while(1) int temp=inf,u=-1,k;/找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路 for(int j=1;j<=n;j+) if(flagj0=0&&temp>disj0) temp=disj0,u=j,k=0; else if(flagj1=0&&temp>disj1) temp=disj1,u=j,k=1; if(temp=inf) break;/S'集合为空或者不联通，算法结束 /更新路径 flaguk=1; for(int l=0;l<Gu.size();l+) int d=disuk+Gul.w,j=Gul.e;/important /4种情况 if(d<disj0) disj1=disj0;cntj1=cntj0;
