ACM常用算法模板

1/96专用模板目录：一、图论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-stepn是素数.n任意15.a^b%c=a^(b%eular(c)+eular(c))%c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21.返回x的二进制表示中从低到高的第i位22.高精度运算+-*/23.超级素数筛选2/96三、数据结构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.zoj2500求两球体积并3/96一、图论1.最大团#includeiostream#includealgorithmusingnamespacestd;intn,m;intcn;//当前顶点数intbest;//当前最大顶点数intvis[50];//当前解intbestn[50];//最优解intmap[50][50];//临界表voiddfs(inti){if(in){for(intj=1;j=n;j++)bestn[j]=vis[j];best=cn;return;}intok=1;for(intj=1;ji;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-ibest){//进入右子树vis[i]=0;dfs(i+1);}}intmain()4/96{while(scanf(%d%d,&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){intp,q;scanf(%d%d,&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf(%d\n,best);}return0;}2.拓扑排序#includeiostream#includecstringusingnamespacestd;intmap[105][105],in[105],vis[105],ans[105],n;intflag;voiddfs(intstep){if(flag)return;if(step==n+1){flag=1;printf(%d,ans[1]);for(inti=2;i=n;i++)printf(%d,ans[i]);printf(\n);return;}for(inti=1;i=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(intj=1;j=n;j++){if(map[i][j]0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;5/96dfs(step+1);vis[i]=0;for(intj=1;j=n;j++){if(map[i][j]0){map[i][j]=-map[i][j];in[j]++;}}}}}intmain(){while(scanf(%d,&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(inti=1;i=n;i++){intt;while(scanf(%d,&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return0;}3．最短路和次短路#includeiostream#includecstdio#includevector#includecstringusingnamespacestd;classNode{public:6/96inte,w;//表示终点和边权};constintinf=(125);intmain(){intci;cinci;while(ci--){vectorNodeG[1005];//用邻接表存边intn,m;cinnm;for(inti=1;i=m;i++){Nodeq;intu;cinuq.eq.w;G[u].push_back(q);}ints,f;//起点和终点cinsf;//dijkstra求最短路和次短路intflag[1005][2];intdis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(inti=1;i=n;i++)dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(intc=0;c2*n;c++)//找最短路和次短路，故要进行2*n次循环也可以改成while(1){inttemp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(intj=1;j=n;j++){if(flag[j][0]==0&&tempdis[j][0])temp=dis[j][0],u=j,k=0;elseif(flag[j][1]==0&&tempdis[j][1])temp=dis[j][1],u=j,k=1;}if(temp==inf)break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(intl=0;lG[u].size();l++){intd=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(ddis[j][0])7/96{dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}elseif(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}elseif(ddis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}elseif(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}intnum=cnt[f][0];//最短路intcc=cnt[f][1];//次短路}return0;}4．SAP模板#includeiostream#includecstdio#includecstringusingnamespacestd;constintinf=(131)-1;constintpoint_num=300;intcap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面ints0,t0,n;//源,汇和点数intfind_path(intp,intlimit=0x3f3f3f3f){if(p==t0)returnlimit;for(inti=0;in;i++)if(dist[p]==dist[i]+1&&cap[p][i]0){intt=find_path(i,min(cap[p][i],limit));if(t0)returnt;if(t0){cap[p][i]-=t;8/96cap[i][p]+=t;returnt;}}intlabel=n;for(inti=0;in;i++)if(cap[p][i]0)label=min(label,dist[i]+1);if(--gap[dist[p]]==0||dist[s0]=n)return-1;++gap[dist[p]=label];return0;}intsap(){//初始化s,ts0=0,t0=n-1;intt=0,maxflow=0;gap[0]=n;while((t=find_path(s0))=0)maxflow+=t;returnmaxflow;}intmain(){intci;while(cincin){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){intx,y,c;cinxyc;x--;y--;cap[x][y]+=c;//因题而异}intans=sap();coutansendl;}return0;}5．已知各点度，问能否组成一个简单图#includeiostream#includecstdio9/96#includealgorithmusingnamespacestd;constintinf=(130);intd[1100];boolcmp(intx,inty){returnxy;}intmain(){intci;scanf(%d,&ci);while(ci--){intn,flag=1,cnt=0;scanf(%d,&n);for(inti=0;in;i++){scanf(%d,&d[i]);if(d[i]n-1||d[i]=0)flag=0;cnt+=d[i];}if(flag==0||cnt%2){printf(no\n);continue;}sort(d,d+n,cmp);for(intl=n;l0;l--){for(inti=1;il&&d[0];i++){d[0]--,d[i]--;if(d[i]0){flag=0;break;}}if(d[0])flag=0;if(flag==0)break;d[0]=-inf;sort(d,d+l,cmp);}if(flag)printf(yes\n);elseprintf(no\n);}10/96return0;}6.KRUSKAL#includeiostream#includealgorithmusingnamespacestd;intu[15005],v[15005],w[15005],fath[15005],r[15005];intans1[15005],ans2[15005];boolcmp(inti,intj){returnw[i]w[j];}intfind(intx){returnfath[x]==x?x:fath[x]=find(fath[x]);}intmain(){intn,m;cinnm;for(inti=1;i=n;i++)fath[i]=i;for(inti=1;i=m;i++)r[i]=i;fo