ACM常用算法模板.docx

专用模板目录：一、图论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#includeusing namespace std;int n,m;int cn;/当前顶点数int best;/当前最大顶点数int vis50;/当前解int bestn50;/最优解int map5050;/临界表void dfs(int i) if(in) for(int j=1;j=n;j+) bestnj=visj; best=cn; return ; int ok=1; for(int j=1;jbest) /进入右子树 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#includeusing 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;j0) mapij=-mapij; inj-; ansstep=i; dfs(step+1); visi=0; for(int j=1;j=n;j+) if(mapij0) 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#include#include#includeusing namespace std;class Node public: int e,w;/表示终点和边权; const int inf=(1ci; while(ci-) vector G1005;/用邻接表存边 int n,m; cinnm; for(int i=1;iuq.eq.w; Gu.push_back(q); int s,f;/起点和终点 cinsf; /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;c2*n;c+) /找最短路和次短路，故要进行2*n次循环也可以改成while(1) int temp=inf,u=-1,k;/找s-S集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路 for(int j=1;jdisj0) temp=disj0,u=j,k=0; else if(flagj1=0&tempdisj1) temp=disj1,u=j,k=1; if(temp=inf) break;/S集合为空或者不联通，算法结束 /更新路径 flaguk=1; for(int l=0;lGu.size();l+) int d=disuk+Gul.w,j=Gul.e;/important /4种情况 if(ddisj0) disj1=disj0;cntj1=cntj0; disj0=d;cntj0=cntuk; else if(d=disj0) cntj0+=cntuk; else if(ddisj1) disj1=d;cntj1=cntuk; else if(d=disj1) cntj1+=cntuk; int num=cntf0;/最短路int cc=cntf1;/次短路 return 0; 4 SAP模板#include#include#includeusing namespace std;const int inf=(131)-1;const int point_num=300;int cappoint_numpoint_num,distpoint_num,gappoint_num;/初始化见main里面 int s0,t0,n;/源,汇和点数 int find_path(int p,int limit=0x3f3f3f3f) if(p=t0) return limit; for(int i=0;i0) int t=find_path(i,min(cappi,limit); if(t0) cappi-=t; capip+=t; return t; int label=n; for(int i=0;i0) label=min(label,disti+1); if(-gapdistp=0 | dists0=n ) return -1; +gapdistp=label; return 0;int sap() /初始化s,t s0=0,t0=n-1; int t=0,maxflow=0; gap0=n; while(t=find_path(s0)=0) maxflow+=t; return maxflow;int main() int ci; while(cincin) /初始化 memset(cap,0,sizeof(cap); memset(dist,0,sizeof(dist); memset(gap,0,sizeof(gap); /初始化cap while(ci-) int x,y,c; cinxyc; x-;y-; capxy+=c;/因题而异 int ans=sap(); coutansendl; return 0;5 已知各点度，问能否组成一个简单图#include#include#includeusing namespace std;const int inf=(1y;int main() int ci;scanf(%d,&ci); while(ci-) int n,flag=1,cnt=0;scanf(%d,&n); for(int i=0;in-1|di0;l-) for(int i=1;il&d0;i+) d0-,di-; if(di0) flag=0;break; if(d0) flag=0; if(flag=0) break; d0=-inf; sort(d,d+l,cmp); if(flag) printf(yesn); else printf(non); return 0;6.KRUSKAL#include#includeusing namespace std;int u15005,v15005,w15005,fath15005,r15005;int ans115005,ans215005;bool cmp(int i,int j)return winm; for(int i=1;i=n;i+) fathi=i; for(int i=1;i=m;i+) ri=i; for(int i=1;iuiviwi; sort(r+1,r+m+1,cmp); int maxn=0,ans=0,k=0; for(int i=1;imaxn) maxn=we; ans1k=ue;ans2k+=ve; return 0; 7.prime求最小生成树语法：prim(Graph G,int vcount,int father); 参数： G：图，用邻接矩阵表示 vcount：表示图的顶点个数 father：用来记录每个节点的父节点返回值：null 注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序： #define infinity 1000000 #define max_vertexes 5 typedef int Graphmax_vertexesmax_vertexes; void prim(Graph G,int vcount,int father) int i,j,k; int lowcostmax_vertexes,closesetmax_vertexes,usedmax_vertexes; for (i=0;ivcount;i+) lowcosti=G0i; closeseti=0; usedi=0; fatheri=-1; used0=1; for (i=1;ivcount;i+) j=0; while (usedj) j+; for (k=0;kvcount;k+)if (!usedk)&(lowcostklowcostj) j=k; fatherj=closesetj; usedj=1; for (k=0;kvcount;k+) if (!usedk&(Gjklowcostk) lowcostk=Gjk; closesetk=j; 8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path); 参数： G：图，用邻接矩阵表示 n：图的顶点个数 s：开始节点 t：目标节点 path：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径： i=t; while (i!=s) printf(%d-,i+1); i=pathi; printf(%dn,s+1); 源程序： int Dijkstra(Graph G,int n,int s,int t, int path) int i,j,w,minc,dmax_vertexes,markmax_vertexes; for (i=0;in;i+) marki=0; for (i=0;in;i+) di=Gsi; pathi=s; marks=1;paths=0;ds=0; for (i=1;in;i+) minc=infinity; w=0;for (j=0;j=dj) minc=dj;w=j; markw=1; for (j=0;jdw+Gwj) dj=dw+Gwj; pathj=w; return dt; 9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path,int success); 参数： G：图，用邻接矩阵表示 n：图的顶点个数 s：开始节点 t：目标节点 path：用于返回由开始节点到目标节点的路径 success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0 顶点标号从0 开始用如下方法打印路径： i=t; while (i!=s) printf(%d-,i+1); i=pathi; printf(%dn,s+1); 源程序： int Bellman_ford(Graph G,int n,int s,int t,int path,int success) int i,j,k,dmax_vertexes; for (i=0;in;i+) di=infinity;pathi=0; ds=0; for (k=1;kn;k+) for (i=0;in;i+) for (j=0;jdi+Gij) dj=di+Gij;pathj=i; success=0; for (i=0;in;i+) for (j=0;jdi+Gij) return 0; success=1; return dt; 10. SPFA#include#include#include#includeusing namespace std;const _int64 maxn=1001000;const _int64 inf=1000100000;struct edge/邻接表 _int64 t,w;/s-t=w; _int64 next;/数组模拟指针;_int64 pmaxn,pfmaxn;/邻接表头节点edge Gmaxn,Gfmaxn;/邻接表_int64 V,E;/点数1-n 边数_int64 dismaxn;_int64 quemaxn,fro,rear;/模拟队列_int64 vismaxn;_int64 inquemaxn;/入队次数bool spfa(_int64 s0) fro=rear=0; for(_int64 i=1;idiss+w) dist=diss+w; if(vist=0) querear+=t,vist=1; inquet+; if(inquetV) return false; if(rear=maxn) rear=0; return true;int main() _int64 ci;scanf(%I64d,&ci); while(ci-) scanf(%I64d%I64d,&V,&E); memset(p,-1,sizeof(p);memset(pf,-1,sizeof(pf); for(_int64 i=0;iE;i+) _int64 u,v,w; scanf(%I64d%I64d%I64d,&u,&v,&w); Gi.t=v; Gi.w=w; Gi.next=pu; pu=i; Gfi.t=u; Gfi.w=w; Gfi.next=pfv; pfv=i; _int64 ans=0; spfa(1);/求第一个点到其他点的最短距离和 for(_int64 i=1;i=V;i+) ans+=disi; /反方向再来一次spfa 求其他点到第一个点的最短距离和 for(_int64 i=1;i=V;i+) pi=pfi; for(_int64 i=0;iE;i+) Gi=Gfi; spfa(1); for(_int64 i=1;i=V;i+) ans+=disi; printf(%I64dn,ans); return 0;11. Kosaraju模板#include#include#include#includeusing namespace std;const int maxn=100000;struct edge int t,w;/u-t=w; int next;int V,E;/点数(从1开始)，边数int pmaxn,pfmaxn;/邻接表原图,逆图edge Gmaxn,Gfmaxn;/邻接表原图,逆图int l,lf;void init() memset(p,-1,sizeof(p); memset(pf,-1,sizeof(pf); l=lf=0;void addedge(int u,int t,int w,int l) Gl.w=w; Gl.t=t; Gl.next=pu; pu=l;void addedgef(int u,int t,int w,int lf) Gfl.w=w; Gfl.t=t; Gfl.next=pfu; pfu=l;/Kosaraju算法,返回为强连通分量个数bool flagmaxn; /访问标志数组int belgmaxn; /存储强连通分量,其中belgi表示顶点i属于第belgi个强连通分量int numbmaxn; /结束时间(出栈顺序)标记,其中numbi表示离开时间为i的顶点/用于第一次深搜,求得numb1.n的值void VisitOne(int cur, int &sig) flagcur = true; for (int i=pcur;i!=-1;i=Gi.next) if (!flagGi.t) VisitOne(Gi.t,sig); numb+sig = cur;/用于第二次深搜,求得belg1.n的值void VisitTwo(int cur, int sig) flagcur = true; belgcur = sig; for (int i=pfcur;i!=-1;i=Gfi.next) if (!flagGfi.t) VisitTwo(Gfi.t,sig); /Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent() int i, sig; /第一次深搜 memset(flag,0,sizeof(flag); for ( sig=0,i=1; i0; -i ) if ( false=flagnumbi ) VisitTwo(numbi,+sig); return sig;int main() while(scanf(%d,&V)=1) init(); for(int i=1;i=V;i+) int u=i,t,w=1; while(scanf(%d,&t)=1&t) E+; addedge(u,t,w,l+); addedgef(t,u,w,lf+); int ans=Kosaraju_StronglyConnectedComponent(); printf(%dn,ans); return 0;12.tarjan模板/自己模板#include#include#include#includeusing namespace std;const int maxn=100000;int V,E;/点数(1) 边数struct edge/邻接表 int t,w;/u-t=w; int next;int pmaxn;/表头节点edge Gmaxn;int l;void init() memset(p,-1,sizeof(p); l=0;/添加边void addedge(int u,int t,int w,int l)/u-t=w; Gl.w=w; Gl.t=t; Gl.next=pu; pu=l;/tarjan算法 求有向图强联通分量int dfnmaxn,lowcmaxn;/dfnu节点u搜索的次序编号,lowcuu或者u的子树能够追溯到的栈中的最早的节点int belgmaxn;/第i个节点属于belgi个强连通分量int stckmaxn,stop;/stck栈int instckmaxn;/第i个节点是否在栈中int scnt;/强联通分量int index;void dfs(int i)dfni=lowci=+index;instcki=1;/节点i入栈stck+stop=i;for(int j=pi;j!=-1;j=Gj.next)int t=Gj.t;/更新lowc数组if(!dfnt)/t没有遍历过dfs(t);if(lowcilowct) lowci=lowct;/t是i的祖先节点else if(instckt&lowcidfnt) lowci=dfnt;/是强连通分量的根节点if(dfni=lowci)scnt+;int t;dot=stckstop-;instckt=0;belgt=scnt;while(t!=i);int tarjan()stop=scnt=index=0;memset(dfn,0,sizeof(dfn);memset(instck,0,sizeof(instck);for(int i=1;i=V;i+)if(!dfni) dfs(i);return scnt;int main() while(scanf(%d,&V)=1) init(); for(int i=1;i=V;i+) int x; while(scanf(%d,&x)=1&x) E+; addedge(i,x,1,l+); int ans=tarjan(); printf(%dn,ans); return 0;/吉大模板 邻