上海交通大学ACM算法模板

《上海交通大学ACM算法模板》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

ACM算法模板集Contents一.常用函数与STL二.重要公式与定理1.FibonacciNumber2.LucasNumber3.CatalanNumber4.StirlingNumber（SecondKind）5.BellNumber6.Stirling'sApproximation7.SumofReciprocalApproximation8.YoungTableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆内接四边形面积公式14.基础数论公式三.大数模板，字符读入四.数论算法1.GreatestCommonDivisor最大公约数2.Prime素数判断3.SievePrime素数筛法4.ModuleInverse模逆元5.ExtendedEuclid扩展欧几里德算法6.ModularLinearEquation模线性方程（同余方程）7.ChineseRemainderTheorem中国余数定理（互素于非互素）8.EulerFunction欧拉函数9.Farey总数9.Farey序列构造10.Miller_Rabbin素数测试，Pollard_rho因式分解五.图论算法1.最小生成树（Kruscal算法）2.最小生成树（Prim算法）3.单源最短路径（Bellman-ford算法）

11.单源最短路径（Dijkstra算法）2.全源最短路径（Folyd算法）3.拓扑排序4.网络预流和最大流5.网络最小费用最大流6.网络最大流（高度标号预流推进）7.最大团8.二分图最大匹配（匈牙利算法）9.带权二分图最优匹配（KM算法）10.强连通分量（Kosaraju算法）11.强连通分量（Gabow算法）12.无向图割边割点和双连通分量13.最小树形图0（N人3）14.最小树形图O（VE）六.几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标4.三角形几个重要的点七.专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数（归并排序）8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配（KMP算法）13.全排列，全组合14.二维线段树15.稳定婚姻匹配16.后缀数组17.左偏树18.标准RMQ-ST19.度限制最小生成树20.最优比率生成树（0/1分数规戈I）

21.最小花费置换2.区间K大数3.LCA-RMQ-ST4.LCA-larjan5.指数型母函数6.指数型母函数(大数据)7.单词前缀树(字典树+KMP)8.FFT(大数乘法)9.二分图网络最大流最小割10.混合图欧拉回路11.无源汇上下界网络流12.二分图最小点权覆盖13.带约束的轨道计数(Burnside引理)14.三分法求函数波峰15.单词计数，矩阵乘法16.字符串和数值hash17.滚动队列，前向星表示法18.最小点基，最小权点基第一章常用函数和STL一.常用函数#includeintgetchar(void);〃读取一个字符/一般用来去押无用字箱char*gets(char*str);〃读取一行字符串#includevoid*malloc(size_tsize);〃动态内存分配，开辟大小为size的空间voidqsort(void*bufzsize_tnum,size_tsize,int(*compare)(constvoid*,constvoid*));〃快速排序Sample:intcompare_ints(constvoid*a,constvoid*b){int*argl=(int*)a;int*arg2=(int*)b;if(*argl<*arg2)return-1;elseif(*argl==*arg2)return0;elsereturn1;}intarray[]={-2,99z0,-743,2,3,4};intarray_size=7;qsort(array,array_size,sizeof(int)zcomparejnts);#include〃求反正弦，argeH,l]z返回值w[-pi/2,+pi/2]doubleasin(doublearg);〃求正弦，arg为弧度,弧度=角度*Pi/180.0,返回值1]doublesin(doublearg);〃求e的arg次方

3doubleexp(doublearg);〃求num的对数，基数为edoublelog(doublenum);〃求num的根

4doublesqrt(doublenum);〃求base的exp次方doublepow(doublebase,doubleexp);#include〃初始化内存，常用来初始化数组void*memset(void*buffer;intchzsize_tcount);memset(the_arrayz0,sizeof(the_array));〃printf是它的变形，常用来将数据格式化为字符串intsprintf(char*buffer;constchar"format,...);sprintf(s,"%d%d"/123z4567);//s=n1234567n〃scanf是它的变形，常用来从字符串中提取数据intsscanf(constchar*buffer;constchar"format,...);Sample:charresult[100]="24hello",str[100];intnum;sprintf(result,"%d%s'

5umzstr);//num=24;str=,'hellon;〃字符串比较，返回值vO代表strlvstr2,=0代表strl=str2,>0代表st「l>str2intstrcmp(constchar*strlzconstchar*str2);常用STL[标准container概要]vectorlistqueuestackpriority_queuesetmap大小可变的向量，类似数组的用法，容易实现删除双向链表队列，empty()zfront()zpop()zpush()栈,empty(),top(),pop(),push()优先队列，empty(),top(),pop(),push()集合关联数组，常用来作hash映射[标准algorithm摘录]for_each()find()replace()copy()remove()reverse()sort()partial_sort()binary_search()merge()对每一个元素都唤起(调用)一个函数查找第一个能与引数匹配的元素用新的值替换元素，O(N)复制(拷贝)元素，O(N)移除元素倒置元素排序，O(Nlog(N))部分排序二分查找合并有序的序列，0(N)[C++String摘录]copy()empty()从别的字符串拷贝判断字符串是否为空

6erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace。替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理1.FibonacciNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610...Formula:F[0]=0;F[l]=1；F[i]=F[i-l]+F[i-2],^(i+11+75p.F[n]==-=l~^——12血V5V5|2jI2.LucasNumber1,3,4,7,11,18,29,47,76,123...Formula:L[n]=n1.CatalanNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012...Formula:C(2n,n)Cln]=—~—(n+1)n=3;Application:1)将n+2边形沿弦切割成n个三角形的不同切割数2)n+1个数相乘，给每两个元素加上括号的不同方法数Sample:

7n=2;(1(23)),((12)3)n=3；(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)2)n个节点的不同形状的二叉树数(严《数据结构》P.155)4)从n*n方格的左上角移动到右下角不升路径数Sample:1.StirlingNumber(SecondKind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中，要求无一为空，其不同的方案数Formula:r0(m=0arnm't1)S(n,m)=—》(-1/*C(m,i)*(m-i)nm!i=oSpecialCases:s(n,o)=oS(n,1)=1S(n,2)=2nl-lS(n,3)=—(3n-3w2n+3)6S(n,n-1)=C(nz2)S(n,n)=12.BellNumbern个元素集合所有的划分数Formula:nB[nl=2S(n,

8i)£=01.Stirling'sApproximation2.SumofReciprocalApproximationEulerGamma=0.57721566490153286060651209;(11>一=lii(n)+EikLexGanvna:(n-»co)8.YoungTableauYoungTableau(杨式图表)是一个矩阵，它满足条件：如果格子[i,j]没有元素，贝旺i+1,"也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素，要么a[i+l,j]>a[i,j]Y[n]代表n个数所组成的杨式图表的个数Formula:Y[l]=1;Y[2]=2;Y(n]=Y[n-1]+(n-1)*Y[n-2];(n>2)9.整数划分将整数n分成k份，且每份不能为空，任意两种分法不能相同1)不考虑顺序for(intp=l;p<=n;p++)for(inti=p;i<=n;i++)for(intj=k;j>=l;j-)dp[i][j]+=dp[i-p][j-l];cout<

9d[n]=(n-1)*(d[n-1]+d[n-2]);8.三角形内切圆半径公式2Sr=；a+b+cp=(a+b+c)/2;S=Vp(p-a)(p-b)(p-c);9.三角形外接圆半径公式abcR=k10.圆内接四边形面积公式a+b*c+dP=——2；S=V(p-a)(p-b)(p-c)(p-d);11.基础数论公式1)模取募an%b=((((a*b)*a)%b)...)%b;2)n的约数的个数n=*32^*33^*.・.*31nll若n满足,则n的约数的个数为(ill+1)(112+1)(113+1)...(inn+1);第三章大数模板typedefinthugeint;〃应不大于，以防乘法时溢出constintBase=1000;constintCapacity=1000;structxnum{intLen;intData[Capacity];xnum():Len(0){}xnum(constxnum&V):Len(V.Len){memcpy(Dataz\/.DatazLen*sizeof*Data);}xnum(intV):Len(O){for(；V>0;V/=Base)Data[Len++]=V%Base;}xnum(charS[]);xnum&operator=(constxnum&V){Len=V.Len;memcpy(DatazV.Data,Len*sizeof*Data);return*this;}

10int&operator[](intIndex){returnData[Index];}intoperator[](intIndex)const{returnData[Index];}voidprint(){printf("%d"zLen==O?O:Data[Len-l]);for(inti=Len-2;i>=0;i)for(intj=Base/10;j>0;j/=10)printf("%d"zData[i]/j%10);}};xnum::xnum(charS[]){intI,J;Data[Len=0]=0;J=1;for(I=strlen(S)-l;I>=0;I-){Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=0;}if(Data[Len]>0)Len++;}intcompare(constxnum&Azconstxnum&B){inti;if(A.Len!=B.Len)returnA.Len>B.Len?1:-1;for(I=A.Len-1;I>=0&&A[I]==B[I];I-);if(I<0)return0;returnA[I]>B[I]?1:-1;}xnumoperator+(constxnum&Azconstxnum&B){xnumR;intI;intCarry=0;for(I=0;I0;I++){if(I0&&R[R.Len-1]==0)R.Len-;returnR;}xnumoperator*(constxnum&A,constintB){intI;if(B==0)return0;xnumRjhugeintCarry=0;for(I=0;I0;I++){if(I0;J++){if(J=R.Len)R[R.Len++]=Carry%Base;

11elseR[I+J]=Carry%Base;Carry/=Base;}}returnR;}xnumoperator/(constxnum&A,constintB){xnumR;intI;hugeintC=0;for(I=A.Len-1;I>=0;I-){C=C*Base+A[I];R[I]=C/B;C%=B;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len—;returnR;}//divxnumoperator/(constxnum&A,constxnum&B){intI;xnumRzCarry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I-){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left0&&R[R.Len-1]==0)R.Len—;returnR;}//modxnumoperator%(constxnum&A,constxnum&B){intI;xnumRzCarry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I-){Carry=Carry*Base+A[I];Left=OjRight=Base-1;while(Left0&&R[R.Len-1]==0)R.Len-;returnCarry;}istream&operator>>(istream&In,xnum&V){charCh;for(V=0;In>>Ch;){V=V*10+(Ch-'0');if(cin.peek()<=',)break;}returnIn;}ostream&operator<<(ostream&Out,constxnum&V){intI;Out<<(V.Len==0?0:V[V.Len-1]);for(I=V.Len-2;I>=0;I-)for(intJ=Base/10;J>0;J/=10)Out<=n-m+l;i--)sum=sum*i;for(i=1;i<=m;i++)sum=sum/i;returnsum;}#defineMAXN9999#defineDLEN4

12classBigNum{private:inta[1000];〃可以控制人数的位数intlen;〃大数长度public:BigNum(){len=1;memset(az0zsizeof(a));}BigNum(constint);BigNum(constchar*);BigNum(constBigNum&);BigNum&operator=(constBigNum&);BigNumoperator+(constBigNum&)const;BigNumoperator-(constBigNum&)const;BigNumoperator*(constBigNum&)const;BigNumoperator/(constint&)const;BigNumoperator人(constint&)const;intoperator%(constint&)const;booloperator>(constBigNum&T)const;voidprint();};BigNum::BigNum(constintb){intc,d=b;len=0;memset(a,0,sizeof(a));while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+l);d=d/(MAXN+1);a[len++]=c;}a[len++]=d;}BigNum::BigNum(constchar*s){intt,k,index/,i;memset(azOzsizeof(a));l=strlen(s);len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-l;i>=0;i-=DLEN){t=O;k=i-DLEN+l;if(klen?T.len:len;for(i=0;iMAXN){t.a[i+1]++;t.a[i]-=MAXN+1;}>if(t.a[big]!=0)t.len=big+l;elset.len=big;returnt;}BigNumBigNum::operator-(constBigNum&T)const{intiJ,big;boolflag;BigNumtl,t2;if(*this>T){tl=*this;t2=T;flag=0;}else{tl=T;t2=*this;flag=l;}big=tl.len;for(i=0;ii)tl.a[j-]+=MAXN;tl.a[i]+=MAXN+1-t2.a[i];}elsetl.a[i]-=t2.a[i];}tl.len=big;

13while(tl.a[len-1]==0&&tl.len>1){tl.len—;big—;}if(flag)tl.a[big-l]=O-tl.a[big-l];returntl;}BigNumBigNum::operator*(constBigNum&T)const{BigNumret;inti,j,up;inttemp,templ;for(i=0;iMAXN){tempi=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+l);ret.a[i+j]=tempi;}else{up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;}ret.len=i+j；while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}BigNumBigNum::operator/(constint&b)const(BigNumret;intizdown=0;for(i=len-1;i>=0;i-){ret.a[i]=(a[i]+down*(MAXN+1))/b;down=a[i]+down*(MAXN+1)-ret.a[i]*b;}ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len—;returnret;}intBigNum::operator%(constint&b)const{inti,d=O;for(i=len-1;i>=0;i-){d=((d*(MAXN+l))%b+a[i])%b;}returnd;}BigNumBigNum::operatorA(constint&n)const{BigNumtzret(l);if(nl){t=*this;inti;for(i=l;i<(constBigNum&T)const{intIn;if(len>T.len)returntrue;elseif(len==T.len){In=len-1;while(a[ln]==T.a[ln]&&In>=0)In--;if(ln>=0&&a[ln]>T.a[ln])returntrue;elsereturnfalse;}elsereturnfalse;}voidBigNum::print(){inti;cout<=0;i—){cout.widthCDLENJjcout.fillCO^jcout<

14constintok=1;intget_val(int&ret){ret=0;charch;while((ch=getchar())>'9'11ch<,0');do{ret=ret*10+ch-'O';}while((ch=getchar())<='9'&&ch>=*0');returnok;}〃带负数intget_val(int&ret){ret=0;charch;boolneg=false;while(((ch=getchar())>'9'11ch<,0')&&ch!='-');if(ch==*-*){neg=true;while((ch=getchar())>'9'11ch<'0');}do{ret=ret*10+ch-10';}while((ch=getchar())<='9*&&ch>=*0');ret=(neg?-ret:ret);returnok;}〃读取整数，可判EOF和EOLconstinteof=-l;constinteol=-2;intget_val(int&ret){ret=Ojcharch;while(((ch=getchar())>'9'||ch<*0,)&&ch!=EOF);if(ch==EOF)returneof;do{ret=ret*10+ch-'0,;}while((ch=getchar())<='9,&&ch>=*0,);if(ch==*

15')returneol;returnok;}〃读取浮点数intget_val(double&ret){ret=Ojdoublebase=O.ljcharch;booldot=false,neg=false;while(((ch=getchar())>'9'11ch<,0')&&ch!=&&ch!=;if(ch=={neg=true;while(((ch=getchar())>*9'11ch<,0')&&ch!=&&ch!=*-');}do{if(ch=={dot=true;continue;}if(dot){ret+=(ch-'O')*base;base*=0.1;}elseret=ret*10+(ch-'O1);}while(((ch=getchar())<=,9'&&ch>=*0')11ch==''');ret=(neg?-ret:ret);returnok;}第四章数论算法1.GreatestCommonDiviso「最大公约数intGCD(intx,inty){intt;while(y>0){t=x%y;x=y;y=t;}returnx;}2.Prime素数判断boolis_prime(intu){if(u==011u==1)returnfalse;if(u==2)returntrue;

16if(u%2==0)returnfalse;for(inti=3;i<=sqrt(u)；i+=2)if(u%i==O)returnfalse;returntrue;}1.SievePrime素数筛法constintM=1000;//M:sizeboolmark[M];//true:primenumbervoidsieve_prime(){memset(mark,true,sizeof(mark));mark[0]=mark[l]=false;for(inti=2;i<=sqrt(M);i++){if(mark[i]){for(intj0〃上式等价于二元一次方程ax-ny=bvoidmodular_linear_equation(inta,intbzintn)

171.ChineseRemainderTheorem中国余数定理//x=b[i](modw[i])zie[1,len-1]//前提条件w[i]>0,且w□中任意两个数互质intchinese_remainder(intb口，intw口，intlen){inti,d,x,y,m,n;ret=0;n=1;for(i=0;i1){ans*=n-1;}returnans;}3.Farey总数〃求MAX以内所有Farey的总数constintMAX=1000100;intn;boolnum[1100];//sqrt(MAX)intprime[1100],total;—int64f[MAX]zinc[MAX];

18voidcal_prime(){inti,j;memset(numzfalse,sizeof(num));total=0;for(i=2;i<1100;i++){if(!num[i]){prime[total++]=i;j=i+i;while(j<1100){num[j]=true;j+=i;}}}}voidcal_farey(){inti,j,k;inc[l]=1;for(i=2;i

19",f[n]);}}1.Farey序列构造〃构造5000以内的Farey序列constintMAX=8000000;inttotal;intnzk;intfarey[2][MAX];voidmake_farey_seq(intxl,intyljntx2,inty2){if(xl+x2>n11yl+y2>n)return;make_farey_seq(x1,yl,xl+x2,yl+y2);total++;farey[0][total]=xl+x2;farey[l][total]=yl+y2;make_farey_seq(xl+x2zyl+y2,x2,y2);}intmain(){intt;scanf("%d%d"z&nz&t);total=l;farey[0][l]=0;farey[l][l]=1;make_farey_seq(04,1/1)；farey[0][total+1]=l;farey[l][total+l]=1;total++;while(t-){scanf("%d"z&k);if(k>total)puts("NoSolution");elseprintf(,,%d/%d

20"/farey[0][k]zfarey[l][k]);}}2.Miller_Rabbin素数测试，Pollard_rho因式分解typedef_int64164;constchar*pformat=n%I64d";164big_rand(I64m){164x=rand();x*=rand();if(x<0)x=-x;returnx%=m;}//x*y%n164mod_mul(I64x,164yz164n){if(x==011y==0)return0;return(((x&l)*y)%n+(mod_mul(x>>lzyzn)<>=1;}returnret;}

21boolMiller_Rabbin(I64n){//O(times*(logN)A3)164i,j,x,m,k;if(n==2)returntrue;if(n<211!(n&l))returnfalse;m=n-1;k=0;while(!(m&l))m>>=1,k++;//binaryscanfor(i=0;i<4;i++){//testtimesx=big_rand(n-2)+2;x=mod_exp(xzm,n);if(x==1)continue;for(j=0;j=k)returnfalse;}returntrue;/*lrjP.218for(i=0;i<20;i++){x=big_rand(n-2)+2;if(mod_exp(xzn-lzn)!=1)returnfalse;}returntrue;*/}164gcd(I64x,164y){if(x>y)std::swap(xzy);while(x){164t=y%x;y=x;x=t;}returny;}164func(I64x,164m){return(mod_mul(x,xzm)+l)%m;}164Pollard(I64n){if(Miller_Rabbin(n))returnn;if(!(n&l))return2;164izxzyzret;i=1;while(true){x=i++;y=func(xzn);ret=gcd(y-xzn);while(ret==1){x=func(x,n);y=func(func(yzn)zn);ret=gcd((y-x+n)%n,n)%n;}if(O0)putchar('');printf(pformatzfactor[i]);}puts("");}const164lim=100000;intmain(){164nztJ;srand((unsigned)time(NULL));scanf(pformatz&t);while(t-){scanf(pformatz&n);

22if(Miller_Rabbin(n))puts("Prime");else{if(!(n&l))puts("2");else{for(minfac=3;minfac=lim){164rn=sqrt(1.0*n);if(rn*rn==n){minfac=rn;cal_factor(rn);}else{minfac=n;cal_factor(n);}}printf(pformatzminfac);puts。);}}}}第五章图论算法1.最小生成树(Kruscal算法)*FunctionName:最小生成树(Kruscal算法)*Description:ZJU1203SwordfishO(E*LogE)#include#include#include#includeusingnamespacestd;structstruct_edges{intbvztv;//bv起点tv终点doublew;〃权值};struct_edgesedges[10100];〃边集structstruct_a{doublex;doubley;};struct_aarr_xy[101];intpoint[101],n,e;//n顶点数，e边数(注意是无向网络)doublesum;intkruscal_fl(intpoint口，intv){inti=v;while(point[i]>0)i=point[i];returni;}boolUDIesser(struct_edgesa,struct_edgesb){returna.w

23if(vl!=v2){sum+=edges[i].w;〃注意sum初始为0point[vl]=v2;j++；}i++；}}intmain(){intkjzj;cin>>n;k=0;while(n!=0){sum=0;k++;for(i=0;i>arr_xy[i].x>>arr_xy[i].y;e=0;for(i=0;i

24,,/k);//cout<

25",sum);〃输Hlsumcin>>n;if(n!=0)printf("

26");}}1.最小生成树(Prim算法)*FunctionName:最小生成树(Prim算法)*Description:ZJU1203SwordfishO(NA2)#include#include#includeusingnamespacestd;doublesum,arrJist[101][101],min;inti,j,k=0,n;structstruct_a{floatx；floaty;};struct_aarr_xy[101];structstruct_b{intpoint;floatlowcost;};struct_bclosedge[101];voidprim(intn)//prim需要准备：n顶点数arjlist□□顶点的邻接矩阵也是从。开始计数{inti,j,k;k=O;

27for(j=0;j>n;while(n!=0){sum=0;k++;for(i=0;i>arr_xy[i].x>>arr^xy[i].y;for(i=0;i

28”,sum);cin>>n;if(n!=O)printf("

29");}}1.单源最短路径(Bellman-ford算法)structnode{inte,v;node(inta=Ozintb=0):e(a),v(b){)};vector>path;intn,p,q;intdist[1000100];/**SPFA(ShortestPathFasterAlgorithm)*Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算*返回值为false,说明队列不为空，存在负权环*/boolSPFA(){intiJ,kznowzl;nodenext;bitset<1000100>vis;

30queueSQ;memset(dist,-l/Sizeof(dist));SQ.push(l);vis[l]=true;dist[l]=0;for(i=0;i<=n;i4-+){I=SQ.size();if(I==0)break;while(I-){now=SQ.front();SQ.pop();vis[now]=false;for(j=path[now].size()-l;j>=O;j—){next=path[now][j];if(dist[next.e]==-l11dist[next.e]>dist[now]+next.v){dist[next.e]=dist[now]+next.v;if(!vis[next.e]){SQ.push(next.e);vis[next.e]=true;}}}}}returnSQ.empty();}4.单源最短路径(Dijkstra算法)*FunctionName:单源最短路径(Dijkstra算法)*Description:贪心，O(N人2),不能有负权intmatrix[200][200]zn;//matrix[][],30000表小无限大，即无边.否则为仃边,其值为边的权值voidDijkstra(intxjnty)〃起点Vx终点Vy{intizjzk,path[40000]zmark[40000];intmin,dist[40000];for(i=l;i<=n;i++){mark[i]=O;dist[i]=matrix[x][i];path[i]=x;}mark[x]=1;do{min=30000;k=0;for(i=l;i<=n;i++)if(mark[i]==0&&dist[i]

31cout<graph[i][k]+graph[k][j])){graph[i][j]=graph[i][k]+graph[k][j];/*最短路径值*/path[i][j]=k;/*最短路径*/}}}}}6.拓扑排序*FunctionName:拓扑排序//degree[]每个结点的入度//f[]每个结点所在的层voidToplogical_sort(){intiJ;boolp=true;top=0;while(p){p=false;top++;for(i=l;i<=n;i++)if(degree[i]==O){p=true;f[i]=top;}for(i=l;i<=n;i++)if(f[i]==top){for(j=l;j<=n;j++)if(map[i][j])degree[j]-;degree[i]="l;}}top-;}7.网络预流和最大流/*网络中求最大流Edmonds_Karp最短增广路算法。(VE八2)参数含义：n代表网络中节点数，第0节点为源点，第n节点为汇点net口口代表剩余网络,0表示无通路path□保存增广路径neck口代表瓶颈，保存增广路径最小容量返回值：最大流量*/constintNMAX=210;

32intnet[NMAX][NMAX];intpath[NMAX],n;intbfs(){queueSQ;intneck[NMAX],i;memset(path,-l,sizeof(path));neck[O]=INT_MAX;SQ.push(l);while(!SQ.empty()){intnow=SQ.front();SQ.pop();if(now==n)break;for(i=l;i<=n;i+4-){if(net[now][i]>0&&path[i]==-1){path[i]=now;neck[i]=min(neck[now]znet[now][i]);SQ.push(i);}}}if(path[n]==-1)return-1;returnneck[n];}intEdmonds_Karp(){intnow,step;intmax_flow=0;while((step=bfs())!=-1){max_flow+=step;now=n;while(now!=-1){intpre=path[now];net[pre][now]-=step;net[now][pre]+=step;now=pre;}}returnmax_flow;}/*网络中求最大流HLPP高度标号预流推进算法0(V人2*E^0.5)参数含义：n代表网络中节点数，第0节点为源点，第n节点为汇点net口口代表剩余网络,0表示无通路earn□代表各点的盈余high口代表各点的高度返回值：最大流量*/constintNMAX=110;intearn[NMAX]znet[NMAX][NMAX]zhigh[NMAX];intn,m;queueSQ;voidpush(intu,intv){intex=min(earn[u]znet[u][v]);earn[u]-=ex;net[u][v]-=ex;earn[v]+=ex;net[v][u]+=ex;}voidrelable(intu){intmmin=INT_MAX;for(i=0;i<=n;i++){if(net[u][i]>0&&high[i]>=high[u]){mmin=min(mmin,high[i]);}}high[u]=mmin+1;}voiddischarge(intu){inti,vn;while(eam[u]>0){vn=0;for(i=0;i<=n&&earn[u]>0;i++){if(net[u][i]>0&&high[u]==high[i]+l){push(uj);vn++;if(i!=n)SQ.push(i);}>if(vn==0)relable(u);}>

33voidinit_preflow(){inti;memset(highzOzsizeof(high));memset(earnzOzsizeof(earn));while(!SQ.empty())SQ.pop();high[O]=n+l;for(i=l;i<=n;i4-+){if(net[O][i]>0){earn[i]=net[0][i];earn[0]-=net[0][i];net[i][0]=net[0][i];net[0][i]=0;if(i!=n)SQ.push(i);}}}inthigh_label_preflow_push(){intij；init_preflow();while(!SQ.empty()){intoverp=SQ.front();SQ.pop();discharge(overp);}returnearn[n];}/*网络中求最大流Dinic算法O(V人2E)适用于稠密图，实际复杂度低于HLPP模板参数含义：n代表网络中节点数，第节点为源点，第n节点为汇点net代表网络，使用前向星表示法存储边dis口代表从源点出发的距离标号path□代表模拟栈中的路径信息cur□代表模拟栈的现场保存返回值：最大流量*/constintNMAX=21000;constintMMAX=250000<

34#defineempty_que2(qf[qnowAl]>=qe[qnowAl])#definesize_que2(qe[qnowAl]-qf[qnowAl])intnzm;intdis[NMAX];intpath[NMAX],deep;intcur[NMAX];boolbfs(){inti,j;memset(disz-l/Sizeof(dis));dis[0]=0;qnow=0;switch_que;push_que(0);switch_que;while(!empty_que2){intI=size_que2;while(I—){intu=pop_que2;for(i=net.start[u];i!=ENDFLAG;i=net.arc[i].next){intv=net.arc[i].v;if(dis[v]==-l&&net.arc[i].cap>net.arc[i].flow){push_que(v);dis[v]=dis[u]+l;if(v==n)returntrue;}}}switch_que;}returnfalse;}intDinic(){intj;intu;intmaxflow=0;while(bfs()){memcpy(curznet.startzsizeof(cur));for(deep=u=O;true;){if(u==n){intneck=INT_MAX,pos;for(i=0;inet.arc[i].flow&&dis[u]+l==dis[net.arc[i].v])break;}cur[u]=i;if(i!=ENDFLAG){path[deep++]=i;u=net.arc[i].v;}else{if(deep==0)break;dis[u]=-l;u=net.arc[path[—deep]],u;}}}returnmaxflow;}8.网络最小费用最大流网络中最小费用最大流O(V*E八2)

35参数含义：n代表网络中的总节点数，第0节点为源点，第n节点为汇点net□□代表剩余网络cost□口代表单位费用path□保存增广路径ecost□源点到各点的最短路算法:初始最小费用和最大流均为0,寻找单位费用最短路在最短路中求出最大流，即为增广路，再修改剩余网络，直到无可增广路为止返回值：最小费用，最大流量constintNMAX=210;intnet[NMAX][NMAX],cost[NMAX][NMAX];intpath[NMAX]zecost[NMAX];intn;boolbellman_ford(){intiJ;memset(pathz-1Zsizeof(path));fill(ecostzecost+NMAX,INT_MAX);ecost[0]=0;boolflag=true;while(flag){flag=false;for(i=0;i<=n;i++){if(ecost[i]==INT_MAX)continue;for(j=0;j<=n;j++){if(net[i][j]>0&&ecost[i]+cost[i][j]

36EDGE(int_u=OJnt_v=0,int_c=0,int_ct=OJnt_f=0):u(_u),v(_v),c叩(_c),flow(_f),8st(_ct){}};constintENDFLAG=-1;structEDGELIST{intstart[NMAX];intlast[NMAX];inttot;EDGEarc[MMAX];voidclear(){tot=ENDFLAG+l;memset(last,ENDFLAG,sizeof(last));}voidpush_back(EDGEedge){edge.next=ENDFLAG;arc[tot]=edge;if(last[edge.u]!=ENDFLAG)arc[last[edge.u]].next=tot;elsestart[edge.u]=tot;last[edge.u]=tot;tot++;}//创建双向弧voidadd_arc(EDGEedge){push_back(edge);push_back(EDGE(edge.vzedge.uzO,INF));}}net;intque[2][NMAX];intqf[2],qe[2]zqnow;#definepush_que(a)(que[qnow][qe[qnow]++]=(a))#definepop_que2(que[qnowAl][qf[qnowAl]++])#defineswitch_queqnowA=1;\qf[qnow]=qe[qnow]=0;#defineempty_que2(qf[qnowAl]>=qe[qnowAl])#definesize_que2(qe[qnowAl]-qf[qnowAl])boolSPFA(){intiJ;bitsetvis;memset(ecost,0x7fzsizeof(ecost));memset(pathz-1,sizeof(path));boolflag=true;qnow=l;switch_que;push_que(s);vis[s]=l;ecost[s]=0;for(j=0;jed.flow&&ecost[ed.v]>ecost[now]+ed.cost){flag=true;ecost[ed.v]=ecost[now]+ed.cost;path[ed.v]=i;if(!vis[ed.v])

37参数含义：s为源点，d为汇点返回值：网络最大流调用函数前的初始化工作:ver置为网络中节点的个数，代表节点i到节点j的流量，vl[i]存放i与相邻的所有节点其它全局变量均初始化为零*/constintVEX=405;〃网络中顶点数constintHMAX=810;〃最大高度的定义，只要大厂顶点的2倍就可以「intf[VEX][VEX];〃流量intc[VEX][VEX];〃边最大容量inth[VEX];〃节点高度inte[VEX];〃节点容量intver;〃节点数Flvectorvl[VEX];〃邻接表,vl[i]存放与i相邻的节点voidPush(intujntv)〃流推进，由节点u推向v0&&h[u]<=h[t]&&h[t]0){if(i=vl[u].size()){Relabel(u);i=0;}elseif(cf>0&&h[u]==h[v]+1)Push(uzv);elsei++；}}intRelabel_lb_Front(intszintd)//s为源点,d为汇点{intuzi/old_h;listl;list:iteratoriter;Init_Preflow(s);iter=l.begin();for(i=0;iold_h){l.erase(iter);l.insert(l.begin()/u);iter=l.begin();}iter++;}returne[ver-1];}9.最大团*FunctionName:最大独立集，最大团

38*Description:PKU1419GraphColoring*团：指G的一个完全子图，该子图不包含在任何其他的完全子图当中*最大独立集：补图的最大团*最大团：指其中包含顶点最多的团#include#include#defineNMAX110boolpath[NMAX][NMAX];intnzmmaxjintdp[NMAX];boolv[NMAX];intseq[NMAX]zseq_pos;//seq记录最大团集合booldfs(intpos,intsize){inti,j,unvis;booltv[NMAX];unvis=0;for(i=pos;immax){mmax=size;seq_pos=0;seq[seq_pos++]=pos+1;returntrue;}returnfalse;}for(i=pos;i0;i++){if(!v[i]){if(unvis+size<=mmax11dp[i]+size<=mmax){returnfalse;}v[i]=true;//U=U\{vi}unvis—;memcpy(tv,v,sizeof(v));for(j=O;j=0;i—){forG=O;j

39for(j=O;j

40nzmax_clique());printf("%d"zseq[0]);for(i=l;i

41n);}}11.最大二分图匹配(匈牙利算法)*FunctionName:最大二分图匹配(匈牙利算法)*Description:HDOJ2063过山车*二分图：指所有顶点分成集合M和N,M或N中任意两个在同一集合中的点互不相连*匹配：一组边顶点分别在两个集合中，并且任意两条边都没有相同顶点*最大匹配：所能得到的最大的边的个数#include#include#includeusingnamespacestd;constintMax=1100;vector>Bmap;intnzm,kznm;intmark[Max];boolflag[Max];booldfs(intpos){inti,pre,tp;for(i=0;i

42"zMax_Match());}}12.带权二分图最优匹配(KM算法)/*带权二分图最优匹配KM算法O（N人4）带权二分图是Kn,n的n阶完全图参数含义：bimap口口代表相等子图，bimap[i][j]表示i和j之间有边tx口，ty□代表交错路径在X和Y上的点lx[]zly口代表X和Y上各点的可行标match[y]=x代表y被x匹配w□□权值返回值：最大权和*/

43constintNMAX=310;boolbimap[NMAX][NMAX];booltx[NMAX]zty[NMAX];intlx[NMAX]zly[NMAX];intmatch[NMAX];intw[NMAX][NMAX]zn;booldfs(intpos){inti;for(i=0;i>path;vector>npath;

44intn,m,sccjintorder[NMAX],order_poszid[NMAX];boolvis[NMAX];voiddfs(intpos){inti,j,l；vis[pos]=true;l=path[pos].size();for(i=0;i=0;i-){if(!vis[order[i]]){ndfs(order[i]);scc++;}}see11.强连通分量(Gabow算法)/*有向图的强连通分量Gabow算法O(E)参数含义：使用邻接表来保存图path原图see强连通个数id[x]=y表示第x个顶点属于y强连通*/#defineNMAX11000vector>path;intn,m,see,step;intorder[NMAX]zorder_pos,id[NMAX];intorder2[NMAX]zorder2_pos;intvis[NMAX];voiddfs(intpos){inti,j,nextj,pre;vis[pos]=step++;order[order_pos++]=pos;order2[order2_pos++]=pos;I=path[pos].size();for(i=0;ivis[next]){order2_pos—；}}}//foriif(order2[order2_pos-1]==pos){//ifposbacktobeginofscc//order2_pos—;}else{return;}do{//recordsccpre=order[order_pos-l];id[pre]=scc;order_pos}while(pre!=pos);see++;}voidGabow(){inti,j,l;〃dfsinoriginalgraphmemset(idz0,sizeof(id));memset(visz0zsizeof(vis));see=step=1;order_pos=order2_pos=0;for(i=l;i<=n;i++){if(vis[i]==0){dfs(i);}}see—

4511.无向图割边割点和双连通分量#definemclear(x)memset((x),0,sizeof((x)))constintMAX=5100;intnzmzdeep;vectorpath[MAX];intvis[MAX]zlow[MAX];vectorcutpoint;〃割点vector>bridge;〃割边，桥intnbcc;〃双连通分量数stack>order;vectorbcc[MAX];〃双连通分显voiddfs(intposzintfather){inti,j,total=0;boolcut=falsejintreback=0;〃处理平行边vis[pos]=low[pos]=deep++;intIs=path[pos].size();for(j=0;je(pos,i);order.push(e);dfs(izpos);if(low[i]>=vis[pos]){nbcc++;bcc[nbcc].clear();pairr;do{r=order.top();order.pop();bcc[nbcc].push_back(r.second);}while(e!=r);bcc[nbcc].push_back(r.first);}total++;low[pos]=min(low[i],low[pos]);if((vis[pos]==1&&total>1)11(visfpos]!=1&&low[i]>=vis[pos]))cut=true;if(low[i]>vis[pos])bridge,push_back(e);}elseif(i!=father){low[pos]=min(vis[i]zlow[pos]);}}if(reback>1)low[pos]=min(low[pos]zvis[father]);if(cut)cutpoint.push_back(pos);}voidfind_cut(){inti;mclear(vis);mclear(low);cutpoint.clear();bridge.clear();nbcc=0;while(!order.empty())order.pop();for(i=l;i<=n;i++){if(vis[i]==0){deep=l;dfs(izi);}}}图的DFS信息构建byoyjpArtg矩阵：g[i][j]->0:无边1:可重复访问边-1:非可重复访问边说明：以为在无向图中u->v访问之后就不能再从v->u访问了故{U,V}访问了之后{V,U)要置-1如果是有向图则没有这个规则gc矩阵:gc[i][j]->0:无边1:树枝边2:反向边3:正向边4：交叉边d数组：顶点的开始访问时间表

46f数组：顶点的结束访问时间表c数组：顶点颜色表0白色-1灰色1黑色p数组：顶点的前驱表I数组：顶点的L值(最顶层的祖先层数)b数组：顶点的度数表关于标号函数LOW。LOW(U)代表的是与U以及U的子孙直接相连的结点的最高辈分(深度)d[U]U苜次被访问时LOW[U]=min(LOW[U],d[W])访问边{U,W}min(LOW[U],LOW[S])U的儿子S的关联边全部被访问时constintmaxn=100;intn,g[maxn][maxn],gc[maxn][maxn];intd[maxn],f[maxn],l[maxn],p[maxn],c[maxn],b[maxn];inttime;voiddfs_visit(intu){〃递归搜索以U为根的深度优先树intv;c[u]=-1;〃置顶点为灰色〃去抻这句之后适用于仃向图(后血设置不可访问亦⑷time++;d[u]=time,l[u]=time;for(v=1;v<=n;v++)if(g[u][v]>0)if(c[v]==0){〃如果v是白色节点g[v][u]=-1;〃不可再访问gc[u][v]=1;〃树枝边b[u]++;〃度数p[v]=u;〃记录父亲节点dist_visit(v);〃递UI搜索以v为根的深度优先树if(l[v]d[u])gc[u][v]=3;〃正向边elsegc[u][v]=4;〃交叉边}}c[u]=1;〃DFS完毕置黑色吧time++;f[u]=time;}voiddfs(){intu;memset(gc,0,sizeof(gc));memset(c,0,sizeof(c));memset(b,0,sizeof(b));time=0;for(u=1;u<=n;u++)if(c[u]==0){p[u]=O;dfs_visit(u);}}16.最小树形图O(N八3)/*最小树形图O(N人3)参数含义：使用邻接矩阵来保存图，邻接表O(VE)

47path原图pre保存最小入弧的权del表示被缩去的点fpre保存最小树形图的逆路径例题：TJU2248ChannelDesign*/constintNMAX=110;constintINF=0x7f7f7f7f;intn;intpath[NMAX][NMAX];intpre[NMAX];boolvis[NMAX]zdel[NMAX];intmin_cost;intfold[NMAX]zfpre[NMAX];voiddfs(intpos){inti;vis[pos]=true;for(i=l;i<=n;i++){if(path[pos][i]!=INF&&!vis[i])dfs⑴；}}boolis_connect(introot){inti;memset(visz0zsizeof(vis));dfs(root);for(i=l;i<=n;i++){if(!vis[i])returnfalse;}returntrue;}//O(NA3)boolmin_tree_graph(introot){inti,jzk;//makesureeverynode(exceptroot)havein-arcif(!is_connect(root))returnfalse;memset(delz0,sizeof(del));min_cost=0;for(i=0;i<=n;i++)fold[i]=fpre[i]=i;while(true){for(i=l;i<=n;i++)path[k][j]-path[pre[j]][j]){path[k][i]=path[k][j]-path[pre[j]][j];fold[i]=j;//recordfoldnode}}}//makenewgraphbreak;}if(i>n){for(i=l;i<=n;i++){if(del[i]||i==root)continue;min_cost+=path[pre[i]][i];}break;}//graphnocycle}//whilehavecyclereturntrue;}//printpathinmintreegraphvoidprint_mtg(introot){inti,total=n;memset(visz0,sizeof(vis));

48for(i=l;i<=n;i++)vis[fpre[i]]=true;for(i=l;i<=n;i++){if(!vis[i]){intpos=i;while(pos!=root){printf("%d<-pos);pos=fpre[pos];}printf("%d

49"zroot);}}}intmain(){inti/m;while(scanf(H%d%d"z&n,&m),!(n==0&&m==0)){memset(pathz0x7fzsizeof(path));while(m-){intx,y,z;scanf("%d%d%d",&xz&yz&z);path[x][y]=min(path[x][y],z);}if(!min_tree_graph(1))puts(nimpossiblen);elseprintf("%d

50"，min_cost);}}17.最小树形图O(VE)constintNMAX=1500;constintINF=0x7f7f7f7f;structLINKT{intls;intadj[NMAX];voidclear(){Is=0;}intoperator[](constintpos){returnadj[pos];}intsize(){returnIs;}voidpush_back(constintpos){adj[ls++]=pos;}};intn;intpath[NMAX][NMAX];LINKTepath[NMAX]znepath[NMAX];intpre[NMAX];boolvis[NMAX]zdel[NMAX];intmin_cost;intfold[NMAX]zfpre[NMAX];voiddfs(intpos){inti;vis[pos]=true;for(i=0;i

51if(j==root)continue;//nocyclei=j;//cyclebeginnodemin_cost+=path[pre[i]][i];for(j=pre[i];j!=i;j=pre[j])for(j=0;jpath[t][j]-path[pre[j]][j]){path[t][i]=path[t][j]-path[pre[j]][j];fold[i]=j;//recordfoldnode}}}//makenewgraphbreak;}if(i>n){for(i=l;i<=n;i+4-){if(del[i]11i==root)continue;min_cost+=path[pre[i]][i];}break;}//graphnocycle}//whilehavecyclereturntrue;}第六章几何算法*COMPUTATIONALGEOMETRYROUTINES*WRITTENBY:LIUYu(C)2003//叉乘//两个点的距离//点到直线距离//返回直线Ax+By+C=0的系数//线段//圆//两个圆的公共面积//矩形//根据下标返回多边形的边//两个矩形的公共面积//多边形，逆时针或顺时针给出x,y//多边形顶点//多边形的边

52//多边形的周长//判断点是否在线段上//判断两条线断是否相交，端点重合算相交//判断两条线断是否平行//判断两条直线断是否相交//直线相交的交点//判断是否简单多边形//求多边形面积//判断是否在多边形上//判断是否在多边形内部//点阵的凸包，返回一个多边形//最近点对的距离#include#include#include#include#includeusingnamespacestd;typedefdoubleTYPE;#defineAbs(x)(((x)>0)?(x):(-(x)))#defineSgn(x)(((x)<0)?(-l):(l))#defineMax(a,b)(((a)>(b))?(a):(b))#defineMin(a,b)(((a)<(b))?(a):(b))#defineEpsilonle-10#defineInfinityle+10#definePi3.14159265358979323846TYPEDeg2Rad(TYPEdeg){return(deg*Pi/180.0);}TYPERad2Deg(TYPErad){return(rad*180.0/Pi);}TYPESin(TYPEdeg){returnsin(Deg2Rad(deg));}TYPECos(TYPEdeg){returncos(Deg2Rad(deg));}TYPEArcSin(TYPEval){returnRad2Deg(asin(val));}TYPEArcCos(TYPEval){returnRad2Deg(acos(val));}TYPESqrt(TYPEval){returnsqrt(val);}structPOINT{TYPEx;TYPEy;TYPEz;POINT():x(0)zy(0)zz(0){};POINT(TYPE_x_,TYPE_y_,TYPE_z_=0):x(_x_)zy(_y_)zz(_z_){};};//crossproductof(o->a)and(o->b)//叉乘TYPECross(constPOINT&a,constPOINT&b,constPOINT&o){return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);}//planarpoints'distance//两个点的距离TYPEDistance(constPOINT&a,constPOINT&b){returnSqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));}structLINE{POINTa;POINTb;UNE(){};LINE(POINT_a_rPOINT_b_):a(_a_),b(_b_){}};〃点到直线距离doublePointToLine(POINTpOZPOINTplZPOINTp2ZPOINT&cp){doubled=Distance(plzp2);doubles=Cross(pl,p2zp0)/d;

53cp.x=pO.x+s*(p2.y-pl.y)/d;cp.y=pO.y-s*(p2.x-pl.x)/d;returnAbs(s);}//返回直线Ax+By+C=0的系数voidCoefficient(constLINE&L,TYPE&A,TYPE&B,TYPE&C){A=L.b.y-L.a.y;B=L.a.x-L.b.x;C=L.b.x*L.a.y-L.a.x*L,b.y;}voidCoefficient(constPOINT&pzconstTYPEa,TYPE&A,TYPE&B,TYPE&C){A=Cos(a);B=Sin(a);C=-(p.y*B+p.x*A);}//线段structSEG{POINTa;POINTb;SEG(){};SEG(POINT_a-zPOINT_b_):a(_aJzb(_b_){};};//圆structCIRCLEB.r)?A:BjconstCIRCLE&N=(A.r>B.r)?B:A;TYPED=Distance(Center(M),Center(N));if((DM.r-N.r)){TYPEcosM=(M.r*M.r+D*D-N.r*N.r)/(2.0*M.r*D);TYPEcosN=(N.r*N.r+D*D-M.r*M.r)/(2.0*N.r*D);TYPEalpha=2.0*ArcCos(cosM);TYPEbeta=2.0*ArcCos(cosN);TYPETM=0.5*M.r*M.r*Sin(alpha);TYPETN=0.5*N.r*N.r*Sin(beta);TYPEFM=(alpha/360.0)*Area(M);TYPEFN=(beta/360.0)*Area(N);area=FM+FN-TM-TN;}elseif(D<=M.r-N.r){area=Area(N);}returnarea;}//矩形//矩形的线段//2//b//II//3||1//a-//0structRECT

54case0:edge.a=rect.ajedge.b=POINT(rect.b.xzrect.a.y);break;case1:edge.a=POINT(rect.b.xzrect.a.y);edge.b=rect.b;break;case2:edge.a=rect.b;edge.b=POINT(rect.a.xzrect.b.y);break;case3:edge.a=POINT(rect.a.x,rect.b.y);edge.b=rect.a;break;default:break;}returnedge;}TYPEArea(constRECT&rect){return(rect.b.x-rect.a.x)*(rect.b.y-rect.a.y);}//两个矩形的公共面积TYPECommonArea(constRECT&AzconstRECT&B){TYPEarea=0.0;POINTLL(Max(A.a.x,Bax),Max(A.a.yzB.a.y));POINTUR(Min(A.b.xzB.b.x),Min(A.b.y,B.b.y));if((LL.x<=UR.x)&&(LL.y<=UR.y)){area=Area(RECT(LLzUR));}returnarea;}//多边形，逆时针或顺时针给出x,ystructPOLY{intn;//n个点TYPE*x;//xzy为点的指针，首尾必须重合TYPE*y;POLY():n(0),x(NULL)zy(NULL){};POLY(int_n_,constTYPE*_x_,constTYPE*_y_){n=_n_;x=newTYPE[n+l];memcpy(xz_x_,n*sizeof(TYPE));x[n]=_x」0];y=newTYPE[n+1];memcpy(y,_y_,n*sizeof(TYPE));y[n]=多边形顶点POINTVertex(constPOLY&poly,intidx){idx%=poly.n;returnPOINT(poly.x[idx]zpoly.y[idx]);}〃多边形的边SEGEdge(constPOLY&poly,intidx){idx%=poly.n;returnSEG(POINT(poly.x[idx]zpoly.y[idx])zPOINT(poly.x[idx+1],poly.y[idx+1]));}〃多边形的周长TYPEPerimeter(constPOLY&poly){TYPEp=0.0;for(inti=0;i

55(((p.x-seg.a.x)*(p.x-seg.b.x)<011(p.y-seg.a.y)*(p.y-seg.b.y)<0)&&(IsEqual(Cross(seg.bzpzseg.a),0)));}〃判断两条线断是否相交，端点重合算相交boolIslntersect(constSEG&uzconstSEG&v){return(Cross(v.azu.bzu.a)*Cross(u.bzv.b,u.a)>=0)&&(Cross(u.azv.bzv.a)*Cross(v.bzu.b,v.a)>=0)&&(Max(u.a.xzu.b.x)>=Min(v.a.x,v.b.x))&&(Max(v.a.xzv.b.x)>=Min(u.a.xzu.b.x))&&(Max(u.a.yzu.b.y)>=Min(vay,v.b.y))&&(Max(v.a.yzv.b.y)>=Min(u.a.y,u.b.y));}〃判断两条线断是否平行boolIsParallel(constLINE&A,constLINE&B){TYPEAl,Bl,Cl;TYPEA2,B2fC2;Coefficient(A,Al,Bl,Cl);CoefficientB,A2ZB2,C2);return(A1*B2==A2*B1)&&((A1*C2!=A2*Cl)||(Bl*C2!=B2*Cl));}〃判断两条直线断是否相交boolIslntersect(constLINE&A,constLINE&B){return!IsParallel(AzB);}〃直线相交的交点POINTIntersection(constLINE&AzconstLINE&B){TYPEAlzBl,C1;TYPEA2,B2,C2;CoefficientA,Al,Bl,Cl);Coefficient(BzA2ZB2,C2);POINT1(0,0);Lx=-(B2*Cl-Bl*C2)/(Al*B2-A2*Bl);I.y=(A2*Cl-Al*C2)/(Al*B2-A2*Bl);returnI;}boolIsInCircle(constCIRCLE&circle,constRECT&rect){return(circle.x-circle.r>=rect.a.x)&&(circle.x+circle.r<=rect.b.x)&&(circle.y-circle.r>=rect.a.y)&&(circle.y+circle.r<=rect.b.y);}〃判断是否简单多边形boolIsSimple(constPOLY&poly){if(poly.n<3)returnfalse;SEGLI,L2;for(inti=0;i

56{if(IsOnSeg(Edge(polyzi),p))returntrue;}returnfalse;}〃判断是否在多边形内部boolIsInPoly(constPOLY&poly,constPOINT&p){SEGL(p,POINT(Infinityzp.y));intcount=0;for(inti=0;iS.b.y)?(S.a):(S.b);if(IsOnSeg(Lzq)){++count;}elseif(!IsOnSeg(L,S.a)&&!IsOnSeg(LzS.b)&&IsIntersect(S,L)){-i-4-count;}}}return(count%2!=0);}//点阵的凸包，返回一个多边形POLYConvexHull(constPOINT*set,intn)//不适用于点少于三个的情况{POINT*points=newPOINTfn];memcpy(pointszset,n*sizeof(POINT));TYPE*X=newTYPE[n];TYPE*Y=newTYPE[n];inti,j,k=0,top=2;for(i=1;i0)||((Cross(points[j]zpoints[k]zpoints[0])==0)&&(Distance(points[0]zpoints[j])=0){top-;}++top;X[top]=points[i].x;Y[top]=points[i].y;}delete[]points;POLYpoly(++top,X,Y);delete[]Xjdelete[]Y;returnpoly;}〃最近点对的距离，WrittenByPrincessSnow#defineMAXN100000POINTpt[MAXN];boolcmp(POINTnl,POINTn2){return(nl.xstart&&pt[mid].x-pt[s].x<=dis)s-;while(e

57doubleClosestPairDistance(intstart,intend){intm=end-start+l,mid,i;doubletlzt2,dis=-l,t;if(m<=3){for(i=start;i=pi+pi)ding-=pi4-pi;if(dlng>pi)ding=pi+pi-ding;latl*=pi/180,Iat2*=pi/180;returnacos(cos(latl)*cos(lat2)*cos(dlng)+sin(latl)*sin(lat2));}//计算距离，r为球半径doubleline_dist(doubler,doublelnglzdoublelatl,doubleIng2,doubleIat2){doubleding=fabs(lngl-Ing2)*pi/180;while(dlng>=pi4-pi)ding-=pi+pi;if(dlng>pi)ding=pi+pi-ding;latl*=pi/180zIat2*=pi/180;returnr*sqrt(2-2*(cos(latl)*cos(lat2)*cos(dlng)+sin(latl)*sin(lat2)));}//计算球面距离，「为球半径doublesphere_dist(doubler,doublelngl,doublelatlzdoubleIng2,doubleIat2){returnr*angle(lngl,latl,Ing2,Iat2);}2.三点求圆心坐标doubleGetRadiusBy3Points(doublexl,doubleyl,doublex2,doubley2,doublex3,doubley3,double&x,double&y){〃由(x・xl)人2+(y-yl)人2=(x・x2)人2+(y-y2)人2得//2*(x2-xl)*x+2*(y2-yl)*y=x2A2-xl人2+y2人2-ylA2〃同理得//2*(x3-x2)*x+2*(y3-y2)*y=x3人2-x2人2+y3人2-y2人2//由行列式解方程得x,ydoubleall,al2za21,a22,bl,b2;doubledzdl,d2;

58all=2*(x3-x2);al2=2*(y3-y2);a21=2*(x2-xl);a22=2*(y2-yl);bl=x3*x3-x2*x2+y3*y3-y2*y2;b2=x2*x2-xl*xl+y2*y2-yl*yl;d=all*a22-al2*a21;dl=bl*a22-al2*b2;d2=all*b2-bl*a21;〃x,y是圆心坐标x=dl/d;y=d2/d;return(xl-x)*(xl-x)+(yl-y)*(yl-y);}1.三角形几个重要的点设三角形的三条边为a,b,c,且不妨假设a<=b<=c三角形的面积可以根据海伦公式算得，如下：s=sqrt(p*(p-a)*(p-b)*(p-c)),p=(a+b+c)/21.费马点(该点到三角形三个顶点的距离之和最小)有个有趣的结论：若三角形的三个内角均小于120度，那么该点连接三个顶点形成的三个角均为120度；若三角形存在一个内角大于120度，则该顶点就是费马点)计算公式如下：若有一个内角大于120度(这里假设为角C),则距离为a+b若三个内角均小于120度，则距离为sqrt((a*a+b*b+c*c+4*sqrt(3.0)*s)/2),其中2.内心----角平分线的交点☆x=(a+b-c)/2,y=(a-b+c)/2,z=(-a+b+c)/2,h=s/p计算公式为sqrt(x*x+h*h)+sqrt(y*y+h*h)+sqrt(z*z+h*h)3.重心----中线的交点计算公式如下：2.0/3*(sqrt((2*(a*a+b*b)-c*c)/4)+sqrt((2*(a*a+c*c)-b*b)/4)+sqrt((2*(b*b+c*c)-a*a)/4))4.垂心垂线的交点计算公式如下：5*(c/2/sqrt(l-cosC*cosC))第七章专题讨论1.树状数组

59*FunctionName:树状数组*Description:HDOJ1166敌兵布阵*减少冗余统计，是线段树的•种变化#includeintdata[50001]zs[50001]zT[50001];inlineintlowbit(intt){returninlineintsum(intend){intsum=0;while(end>0){sum+=T[end];end-=lowbit(end);}returnsum;}inlinevoidplus(intposzintnumzintcount){while(pos<=count){T[pos]+=num;pos+=lowbit(pos);}}intmain(){charbuffer[10];inti,j,tznza,b;scanf("%d"z&t);for(i=l;i<=t；i++){scanf("％d"，&n);T[0]=s[0]=data[0]=0;for(j=l;j<=n;j++){scanf("％cT,&data[j]);s[j]=s[j・1]+data[j];T[j]=s[j]-s[j-lowbit(j)];}printf("Case%d:

60",i);while(scanf(H%s",buffer)==1&&buffer[O]!='E'){scanf("%d%d"z&a,&b);switch(buffer[O]){case,Q':printf(,'%d

61H/sum(b)-sum(a)+data[a]);break;case'A':plus(a,b,n);data[a]+=b;break;case'S':plus(az-b,n);data[a]-=b;break;}}}}2.字典树*FunctionName:字典树(多路杳找树)*Description:HDOJ1075WhatAreYouTalkingAbout*易于字符保存，插入和查找，时间复杂度都是线性#include#includeusingnamespacestd;structtrie{trie*next[26];intindex;};trie*thead;chardic[1000000][20];inlinetrie*newnode(){inti;trie*t;t=(trie*)malloc(sizeof(trie));memset(tzOzsizeof(trie));returnt;}voidinsert(trie*szcharx[],intpos){intijtrie*t;for(i=0;x[i];i++){if(s->next[x[i]-*a'])s=s->next[x[i]-'a'];

62else{t=newnode();s->next[x[i]-'a']=t;s=t;}}//fors->index=pos;}voiddeltrie(trie*s){inti;for(i=0;i<26;i++){if(s->next[i])deltrie(s->next[i]);}free(s);s=NULL;}intfind(trie*szcharx[]){inti;if(x[0]==0)return-1;for(i=0;x[i];i++){if(s->next[x[i]-'a'])s=s->next[xtij-'a*];elsebreak;}if(x[i]==0)returns->index;elsereturn-1;}intmain(){inttznjJ,all;charword[20]zmars[20],ch;thead=newnode();while(scanf("%s,,/word)==l)if(word[0]=='S')break;i=l;while(scanf("%s"zdic[i])==l&&dic[i][0]!=,E'){scanf("%s",mars);insert(thead,marszi);i+4-;}all=i;while(scanf("%s",word)==l)if(word[0]=='S')break;getchar();j=0;while(scanf("%c"z&ch)==l&&ch!=E){if(ch>='a'&&ch<=*z'){mars[j]=ch;j++;}else{mars[j]=O;t=find(thead,mars);j=0;if(t>0)printf(H%sHzdic[t]);elseif(mars[O]!=O)printf(n%s,,/mars);printf("%c"zch);}}//whiledeltrie(thead);}3.后缀树*Description:PKU2774LongLongMessage*有效的支持字符串匹配和查询#include#include

63#defineNUM27#defineSTARTCHAR'a,#defineSPECIALCHAR#defineERROR-1#defineTYPE11#defineTYPE22#defineLEAF1#defineNOTLEAF2structSuffixTrie{intStart,End;SuffixTrie*Next[NUM];SuffixTrie*Link;SuffixTrie*Father;intFlag;intLength;};charstr[100010],buf[100010];SuffixTriehead;SuffixTrie*P,*G,*U,*VZ*q;intW[3],len,Ien2;voidCreateNode(SuffixTrie*&Node){inti;Node=(SuffixTrie*)malloc(sizeof(SuffixTrie));Node->Start=Node->End=Node->Length=ERROR;for(i=0;iNext[i]=NULL;Node->Link=Node->Father=NULL;Node->Flag=LEAF;}voidInit(SuffixTrie&hzchars[]){inti;h.Start=h.End=ERROR;for(i=0;iNext[s[W[O]]-STARTCHAR];old=0;while(W[2]>(t->End)-(t->Start)+1+old){old+=(t->End-t->Start+l);t=t->Next[s[W[0]+old]-STARTCHAR];}if(W[2]==(t->End)-(t->Start)+1+old){V=t;P->Link=V;returnTYPE1;}else{CreateNode(newt);newt->Start=t->Start;newt->End=t->Start+W[2]-old-1;newt->Father=t->Father;newt->Length=newt->Father->Length+newt->End-newt->Start+l;t->Father->Next[s[t->Start]-STARTCHAR]=newt;t->Start=newt->End+l;newt->Next[s[t->Start]-STARTCHAR]=t;t->Father=newt;V=newt;P->Link=V;returnTYPE2;}}intInsert(SuffixTrie*Node,intstart,chars[]){inti,posbegin,posend;SuffixTrie*t;if(Node->Next[s[start]-STARTCHAR]==NULL){CreateNode(Node->Next[s[start]-STARTCHAR]);Node->Next[s[start]-STARTCHAR]->Start=start;Node->Next[s[start]-STARTCHAR]->End=len-1;Node->Next[s[start]-STARTCHAR]->Father=Node;Node->Next[s[start]-STARTCHAR]->Length=Node->Length+len-start;Node->Flag=NOTLEAF;P=Node;returnTYPE1;}else{posbegin=Node->Next[s[start]-STARTCHAR]->Start;

64posend=Node->Next[s[start]-STARTCHAR]->End;for(i=posbegin;i<=posend;i++){if(s[i]!=s[start+i-posbegin])break;}if(i==posend+1){returnInsert(Node->Next[s[start]-STARTCHAR]zstart+i-posbeginzs);}else{CreateNode(t);t->Start=posbegin;t->End=i-1;t->Flag=NOTLEAF;Node->Next[s[start]-STARTCHAR]->Start=i;t->Next[s[i]-STARTCHAR]=Node->Next[s[start]-STARTCHAR];t->Next[s[i]-STARTCHAR]->Father=t;Node->Next[s[start]-STARTCHAR]=t;t->Father=Node;t->Length=Node->Length+t->End-t->Start+l;Insert(tzstart+i-posbegin,s);G=Node;P=t;returnTYPE2;}}}intSelect(intstart,chars[]zinttype){intresultl,result2zresult;if(type==TYPE1){U=P->Link;result=Insert(Uzstart+U->Lengthzs);}else{U=G->Link;if(G->Link==G){W[0]=P->Start+l;W[l]=P->End;W[2]=P->End-P->Start;}else{W[0]=P->Start;W[l]=P->End;W[2]=P->End-P->Start+1;}if(W[2]==0){V=G;P->Link=V;result=Insert(Vzstart,s);}else{resultl=FindV(s);result2=Insert",start+V->Length,s);if(resultl==TYPE2){G=P->Father;result=resultl;}elseresult=result2;}}returnresult;}voidBuildSuffixTrie(SuffixTrie&hzchars[]){inti;inttype;len=strlen(s);CreateNode(h.Next[s[0]-STARTCHAR]);h.Next[s[O]-STARTCHAR]->Start=O;h.Next[s[O]-STARTCHAR]->End=len-l;h.Next[s[O]-STARTCHAR]->Father=&h;h.Next[s[O]-STARTCHAR]->Length=h.Length+h.Next[s[O]-STARTCHAR]->End-h.Next[s[O]-STARTCHAR]->Start+l;h.Flag=NOTLEAF;type=TYPE1;P=&h;for(i=1;iNext[i]!=NULL){DeleteSuffixTrie(Node->Next[i]);Node->Next[i]=NULL;}}free(Node);}intFindString(intstart,chars[]){intresultjinti;inttemp;SuffixTrie*x;x=P->Next[s[start]-STARTCHAR];result=P->Length;if(x==NULL){P=P->Link;returnresult;}temp=0;for(i=start;iStart+i-start-temp>x->End){temp=i-start;P=x;x=x->Next[s[start+temp]-STARTCHAR];if(x==NULL)break;}if(s[i]!=str[x->Start+i-start-temp])break;result+4-;}

65P=P->Link;returnresult;}intSearch(SuffixTrie&hzchars[]){intresultjinti;inttemp;Ien2=strlen(s);result=0;P=&head;for(i=0;iLength,s);if(result=Ien2-i)break;}returnresult;}intmain(){intresult;while(scanf("%s"rstr)!=EOF){Init(headzstr);BuildSuffixTrie(headzstr);scanf(,'%s"/buf);result=Search(headzbuf);printf(,,%d

66"/result);}}4.线段树*FunctionName:线段树*Description:HDOJ1542Atlantis*用于表示区间线段#include#includeusingnamespacestd;typedefstructITREE_NODE{ITREE_NODE*pLChild,*pRChild;doubleleft,right;//左端点，右端点doublemeasure;//测度intcount;//覆盖计数器intlines;//独立线段数intIbound,rbound;//覆盖左、右顶点的线段数目}*PITREE_NODE;inlinevoidsafe_add(int&v,intvalue){v+=value;if(v<0)v=0;}voiditree_splite(constdouble*pListzPITREE_NODEpParent,constintiLeft,constintiRight){if(iRight-iLeft<=1)return;intiMid=(iLeft+iRight)>>1;pParent->pLChild=newITREE_NODE;pParent->pRChild=newITREE_NODE;memset(pParent->pLChild,0,sizeof(ITREE_NODE));memset(pParent->pRChild,0,sizeof(ITREE_NODE));pParent->pLChild->left=pList[iLeft];pParent->pLChild->right=pList[iMid];pParent->pRChild->left=pList[iMid];pParent->pRChild->right=pList[iRight];

67itree_splite(pList,pParent->pLChild,iLeft,iMid);itree_splite(pListzpParent->pRChild,iMid,iRight);}PITREE_NODEitree_generate(constdouble*pList,constintiListCount){PITREE_NODEpRoot=newITREE_NODE;memset(pRootz0,sizeof(ITREE_NODE));pRoot->left=pList[O];pRoot->right=pList[iListCount-1];itree_splite(pList,pRoot,0,iListCount-1);returnpRoot;}voiditree_destroy(PITREE_NODEpParent){if(pParent==NULL)return;if(pParent->pLChild)itree_destroy(pParent->pLChild);if(pParent->pRChild)itree_destroy(pParent->pRChild);deletepParent;}inlinevoiditree_measure(PITREE_NODEpNode){if(pNode->count>0)pNode->measure=pNode->right-pNode->left;elseif(pNode->pLChild&&pNode->pRChild)pNode->measure=pNode->pLChild->measure+pNode->pRChild->measure;elsepNode->measure=0;}inlinevoiditreeJines(PITREE_NODEpNode){if(pNode->count>0){pNode->lines=1;}elseif(pNode->pLChild&&pNode->pRChild){if(pNode->pLChild->rbound&&pNode->pRChild->Ibound){pNode->lines=pNode->pLChild->lines+pNode->lines-1;}else{pNode->lines=pNode->pLChild->lines+pNode->lines;}}else{pNode->lines=0;}}//插入的时候value=1,删除的时候value=-1voiditree_update(PITREE_NODEpParentzconstdoubleleft,constdoublerightJntvalue){if(pParent->left==left&&pParent->right==right){safe_add(pParent->count,value);safe_add(pParent->Ibound,value);safe_add(pParent->rbound,value);itree_measure(pParent);itree_lines(pParent);}else{if(pParent->pLChild->right>left){if(pParent->pLChild->right>=right){itree_update(pParent->pLChild,left,right,value);}else{itree_update(pParent->pLChild,leftzpParent->pLChild->rightzvalue);itree_update(pParent->pRChild,pParent->pRChild->left:,right,value);}}else{itree_update(pParent->pRChild,left,right,value);}itree_measure(pParent);itree_lines(pParent);if(left==pParent->left)safe_add(pParent->Ibound,value);if(right==pParent->right){safe_add(pParent->rboundzvalue);}}}voiditree_insert(PITREE_NODEpParent,constdoubleleft,constdoubleright){itree_update(pParent,left,right,1);}voiditree_delete(PITREE_NODEpParent,constdoubleleft,constdoubleright){itree_update(pParentzleft,right,-1);}structEVENT{doublex,ylzy2;inttype;};boolcmp(constEVENT&a,constEVENT&b){returna.x

68doubleY[200];doubletsize=0.0;intmain(){doublexl,x2,yl,y2;inti,n,n2,cas=0;while(scanf(n%d"z&n)==1&&n){cas++;n2=n<<1;for(i=0;i0)tsize+=pRoot->measureFunctionName:二叉堆*Description:父结点的键值总是大於或等於任何一个子节点的键值(env[i].x-env[i-l].x);elsetsize=0.0;itree_update(pRoot,env[i].ylzenv[i].y2,env[i].type);}itree_destroy(pRoot);printf("1estcase#%d

69fbtalexploredarea:%.2lf

70

71"zcas,tsize);}return0;}5.并查集*FunctionName:并查集*Description:集合操作，并，除，判断constintMax=1000;typedefintElemlype;intParent[Max],Rank[Max];intFind(intx){inttemp=x,root,w;〃搜寻根节点while(Parent[x]!=0)x=Parent[x];root=x;x=temp;〃压缩路径while(Parent[x]!=0){w=Parent[x];Parent[x]=root;x=w;}returnroot;}intUnion(intx,inty){intuzvzroot;u=Find(x);v=Find(y);if(Rank[u]<=Rank[v]){root=Parent[u]=v;if(Rank[u]==Rank[v])Rank[v]+4-;>elseroot=Parent[v]=u;returnroot;}

725.二叉堆103020/\/\3438_3024*便於寻找父节点和子节点constintMax=1000;typedefintElemlype;ElemlypeHe叩[Max];intSift_Up(inti)//上移{Elemlypetemp;boolflag;flag=true;if(i==1)return0;do{if(Heap[i]>Heap[i/2]){temp=Heap[i];Heap[i]=Heap[i/2];Heap[i/2]=temp;}elseflag=false;i/=2;}while(i>l11flag);return1;}intSift_Down(intijntn)//卜.移{boolflag;Elem7ypetemp;flag=false;if(2*i>n)return0;do{i*=2;if(i+l<=n&&Heap[i+1]>Heap[i])i++;if(Heap[i/2]=x)Sift_Up(i);elseSift_Down(izn);returnx;}intDelete_Max(int&n)〃输出最大值{ElemTypex;x=Heap[1];Delete(nz1)；retumx;}intMake_Heap(intn)〃转换为大顶堆{inti;for(i=n/2;i>=1;i—)Sift_Down(izn);returnn;}intHeapSort(intn)〃非降序排序{inti;Elemlypetemp;Make_Heap(n);for(i=n;i>=2;i—){temp=Heap[i];Heap[i]=Heap[l];Heap[l]=temp;Sift_Down(lzi-l);)return1;}

735.逆序数(归并排序)*FunctionName:逆序数(归并排序)*Description:N*Log(N)〃逆序数值存放在anti中intp[MAX],t[MAX]zanti=0;voidmerge(intfirst,intlast){intmid=(first+last)/2;intil=0,12=first,i3=mid+1;while(i2<=mid&&i3<=last){if(p[i2]>p[i3]){t[il++]=p[i3++];anti+=mid-i2+l;}elset[il++]=p[i2++];>while(i2<=mid)t[il++]=p[i2++];while(i3<=last)t[il++]=p[i3++];il=first;i2=0;while(i2#include#includeusingnamespacestd;#defineMax210intnzm,a[Max][Max];structinf{intlzr,p;intv;}tree[Max];inttpznow;queueSQ;charv[Max];intmain(){intirj;introot,pt,tv;while(scanf(",%d%d"/&nzam)){if(n==O&&m==0)break;memset(treezOzsizeof(tree));memset(az0zsizeof(a));memset(v/3,sizeof(v));while(!SQ.empty())SQ.pop();for(i=l;i<=n;i++){scanf(,,%d%dM/&rootz&tree[i].v);if(tree[root].I==0){tree[root].l=i;v[root]-;tree[i].p=root;}else{pt=tree[root].l;while(tree[pt].r!=0)pt=tree[pt].r;

74tree[pt].r=i;v[pt]-=2;tree[i].p=pt;}}for(i=l;i<=n;i++)if(v[i]==3)SQ.push(i);while(!SQ.empty()){now=SQ.front();SQ.pop();a[now][l]=tree[now].v;for(i=l;i<=m;i++)a[now][i]=a[now][i]

75",a[tree[O].l][m]);}}9.欧拉路*FunctionName:欧拉路*Description:ZJU2730Necklace*欧拉路的构造方法：*若图连同且度为奇数的节点不超过2个，则该图可以构造出欧拉路*先选一个度为奇数的节点(若没有就任选•个度为偶数的节点)*再以该节点为起点，用dfs遍历所有的弧(每条弧只遍历一次)，遇到死胡同就回溯*在每次回溯时将所在弧按顺序记录下来,这组弧的排列就组成了一条欧拉路#include#defineMAXN50voidfind_path_euler(intnzintmat[][MAXN],intnow,int&step,int*path){inti;for(i=n-l;i>=0;i-)while(mat[now][i]){mat[now][i]—,mat[i][now]—;find_path_u(n,mat,i,step,path);}path[step++]=now;}intmain(){intn;inta[MAXN][MAXN];int\,j,cntzmmin;intb[10000]zc[10000];while(scanf(',%d,,z&n)!=EOF){for(i=0;i

76",mmin-1);for(i=0;i

77M);}}

7810.八数码*FunctionName:八数码Eight(SpecialJudge)*Description:搜索+状态hash*PKU(1077)HDOJ(1043)ZOJ(1217)*BFS广搜PKU(312ms)HDOJ(TLE)ZOJ(TLE)*BFS2双向广搜PKU(31ms)HDOJ(1325ms)ZOJ(TLE)*以上均是每次计算的运行耗时，ZOJ的可以全部计算后保存状态#include#include#include#includeusingnamespacestd;charinput[100];intstate[10],s_numzel0[10],fac_n[10];charhash_T[400000]zstep[10000]zhash_T2[400000];structinf{intpos;charmode;};queueSQ;queueSQ2;intnum_pos(intnumjntxjnty){inttemp=(x-l)*3+y;if(temp==num%10)return9;if(temp>num%10)return(num/el0[9-temp+l])%10;elsereturn(num/el0[9-temp])%10;}intstate_pos(intnumjntxjnty){inttemp=(x-l)*3+y;if(temp==state[9])return9;if(temp>state[9])returnstate[temp-l];elsereturnstate[temp];>inlineintmove(intnum,charop){intt0,tl/t2;switch(op){case'r':if(num%10%3==0)return0;returnnum+1;case'r：if((num-l)%10%3==0)return0;returnnum-1;case*u':if(num%10-3<=0)return0;tO=9-num%10+l;tl=num/elO[tO];t2=tl%1000;tl=tl-t2+(t2%100)*104-t2/100;tl*=elO[tO];return(tl+((num%elO[tO])-3));case'd':if(num%10+3>9)return0;tO=9-num%10+1-3;tl=num/el0[t0];t2=tl%1000;tl=tl-t2+(t2%10)*100+t2/10;tl*=elO[tO];return(tl+((num%elO[tO])+3));}}boolbe_solved(){intijzanti=0;for(i=l;i<=8;i++)for(j=l;j

79elsereturntrue;}inlineinthash(intnum){intdig[10],i=9,j,sum,anti;if(num==O)return-1;while(num)dig[i]=num%10,num/=10,i—;sum=(9-dig[9])*fac_n[8];for(i=l;i<9;i4-+){for(anti=0J=l;j=0&&hash_T[to_hash]==0)hash_T[to_hash]='r'zSQ.push(to_num);to__num=move(k/r);to_hash=hash(to_num);if(to_hash>=0&&hash_T[to_hash]==0)hash_T[to_hash]=T,SQ.push(to_num);to_num=move(k/u');to_hash=hash(to_num);if(to_hash>=0&&hash_T[to_hash]==0)hash_T[to_hash]='u*zSQ.push(to_num);to_num=move(kz'd');to_hash=hash(to_num);if(to_hash>=0&&hash_T[to_hash]==0)hash_T[to_hash]='d*,SQ.push(to_num);}}voidBFS2(){intto_numzto_hashj;char*phashz*phash2;charop;infkzt;memset(hash_10,sizeof(hash_T));memset(hash_T2z0zsizeof(hash_T2));while(!SQ2.empty())SQ2.pop();k.pos=s_num;k.mode=l;SQ2.push(k);k.pos=123456789;k.mode=2;SQ2.push(k);hash_T[hash(s_num)]='s';hash_T2[hash(123456789)]='e';while(!SQ2.empty()){k=SQ2.front();SQ2.pop();to_hash=hash(k.pos);if(k.mode==l)if(hash_T2[to_hash]!=0)break;elsephash=hash_Xphash2=hash_T2;if(k.mode==2)if(hash_T[to_hash]!=0)break;elsephash=hash_T2zphash2=hash_T;t=k;t.pos=move(k.pos/r');to_hash=hash(t.pos);if(to_hash>=0&&phash[to_hash]==0)

80phash[to_hash]=FunctionName:高斯消元法*Description:求解线性方程组**voidexchange_col(intpljntp2,intn)r'zSQ2.push(t);t.pos=move(k.poszT);to_hash=hash(t.pos);if(to_hash>=0&&phash[to_hash]==0)phash[to_hash]=T,SQ2.push(t);t.pos=move(k.pos/u');to_hash=hash(t.pos);if(to_hash>=0&&phash[to_hash]==0)phash[to_hash]='u',SQ2.push(t);t.pos=move(k.pos/d');to_hash=hash(t.pos);if(to_hash>=0&&phash[to_hash]==0)phash[to_hash]=d,SQ2.push(t);}i=0;to_hash=hash(k.pos);to_num=k.pos;while(hash_T[to_hash]!='s'){switch(step[i++]=hash_T[to_hash]){case*r':op=T;break;caseT:op='r';break;case'u':op=*d';break;case'd':op='u';break;}to_num=move(to_num,op);to_hash=hash(to_num);}while(i>0)printf("%cnzstep[—i]);to_hash=hash(k.pos);to_num=k.pos;while(hash_T2[to_hash]!=*e'){switch(hash_T2[to_hash]){caseT:op=T;break;caseT:op='r';break;case*u':op='d';break;case'd':op='u';break;}printf(,,%c",op);to_num=move(to_numzop);to_hash=hash(to_num);}}intmain(){intij;for(el0[0]=lj=l;i<=9;i4-+)el0[i]=el0[i-l]*10;for(fac_n[0]=0zfac_n[l]=lj=2;i<=9;i++)fac_n[i]=fac_n[i-l]*i;while(gets(input)){for(i=strlen(input)-lj=8;i>=0;i—){if(input[i]!=*'){if(input[i]=='x,)state[9]=j+l;elsestate[j-]=input[i]-'O';}}for(s_num=0/i=9zj=l;i>0;i--/j*=10)s_num+=state[i]*j;if(!be_solved()JprintfC'unsolvableXn'*);else{BFS2();printf("

81");}}}11.高斯消元法*交换pl行和p2行的所有数据**boolgauss(intn)

82*求解系数矩阵为n的线性方程组，方程组无解返回false,否则true**xl=xO-f(xO)/f(xO)牛顿迭代法constintnum=100;doublematrix[num][num+1];〃系数矩阵，从0开始doubleans[num];〃结果数组voidexchange_col(intpl,intp2,intn)〃交换pl行和p2行的所有数据*doublet;inti;for(i=0;i<=n;i++)t=matrix[pl][i]rmatrix[pl][i]=matrix[p2][i]zmatrix[p2][i]=t;}boolgauss(intn)〃求解系数矩阵为n的线性方程组*inti,j,k;intp;doubler;for(i=0;imatrix[p][i])p=j;}if(matrix[p][i]==0)returnfalse;if(p!=i)exchange_col(i,pzn);for(j=i+1;j=0;i-){〃获得结果ans[i]=matrix[i][n];for(j=n-l;j>i;j-)ans[i]-=matrix[i][j]*ans[j];ans[i]/=matrix[i][i];}returntrue;}12.字符串匹配(KMP算法)*FunctionName:字符串匹配(KMP算法)*Description:O(N+M)voidget_nextval(conststring&s,int*p){inti=0,j=-l;p[0]=-1;while(i

83elsej=next[j];}if(j>sl.size())returni-sl.size();elsereturn-1;}12.全排列，全组合*FunctionName:全排列,全组合voidcreateper(intn)〃全排列{inttotal/,j,k,t,*a=newint[n]ztop;total=1;for(i=l;i<=n;i++){a[i]=i;total*=i;}for(i=l;i

84Mza[n]);for(i=l;ia[k])k—;t=a[j-l];a[j-l]=a[k];a[k]=t;top=(j+n-l)/2;for(k=j;k<=top;k++){t=a[k];a[k]=a[n-k+j];a[n-k+j]=t;}for(j=l;j

85"za[n]);}}voidcreatefab(intmjntn)〃全组合{intizjzlcountz*a=newint[n+2];for(i=l;iv=n;i++)a[i]=i;a[n+l]=m+l;for(j=l;jvn;j++)printf(n%dlcount=l;while(a[l]0;i—){if(a[i]

86",a[n]);lcount++;break;}}}}二维线段树*FunctionName:二维线段树RMQ*Description:HDOJ1823LuckandLove#include#include#includeusingnamespacestd;#defineNMAX500000#defineMQ(xzy)((x)>(y)?(x):(y))structnode{intM;}mem[NMAX];node*pleftz*pright;node*ytree;intleft,right;intmem_pos;node*new_node(){node*pt=&mem[mem_pos+4-];memset(ptz0zsizeof(node));pt->M=-l;//maximumorminimumreturnpt;}node*create_tree(intxlzintylzintx2zinty2,boolflag)

87{node*root=new_node();if(flag){//firstdimensionroot->left=xl;root->right=yl;root->ytree=create_tree(xl,yl,x2,y2zfalse);if(xl!=yl){intmid=(xl+yl)/2;root->pleft=create_tree(xlzmid,x2,y2,true);root->pright=create_tree(mid+lzyl,x2zy2,true);}}else{//seconddimensionroot->left=x2;root->right=y2;if(x2!=y2){intmid=(x2+y2)/2;root->pleft=create_tree(xlzyl,x2,mid,false);root->pright=create_tree(xlzyl,mid+1,y2zfalse);}}returnroot;}voidupdate(node*root,intdl,intd2,intv,boolflag){intmid=(root->left+root->right)/2;if(flag){//firstdimensionupdate(root->ytreezdl,d2,v,false);if(root->leftright){if(dl<=mid){update(root->pleftzdl,d2,vztrue);}else{update(root->prightzdlzd2,v,true);}}}else{//seconddimensionif(root->left==root->right){root->M=MQ(root->MZv);}else{if(d2<=mid){update(root->pleft,dl,d2,v,false);}else{update(root->prightzdlzd2,v,false);}root->M=MQ(root->pleft->MZroot->prightintquery(node*root,intxl,intyl,intx2,inty2zboolflag){intlmqzrmqjintmid=(root->left+root->right)/2;if(flag){//firstdimensionif(root->left==xl&&root->right==yl){returnquery(root->ytreezxl,ylzx2,y2,false);}else{if(yl<=mid){returnquery(root->pleftzxlzyl,x2zy2,true);}if(xl>mid){returnquery(root->pright/xl,yl,x2,y2,true);}Imq=query(root->pleftzxlzmid,x2,y2,true);rmq=query(root->pright,mid+1,yl,x2,y2,true);}}else{//seconddimensionif(root->left==x2&&root->right==y2){returnroot->M;}else{if(y2<=mid){returnquery(root->pleftzxlzyl,x2zy2,false);}if(x2>mid){returnquery(root->prightzxl,ylzx2,y2,false);}Imq=query(root->pleftzxl,yl,x2,mid,false);rmq=query(root->prightzxlzylzmid+l,y2,false);}}returnMQ(lmqzrmq);}intmain(){intm;charcmd;while(scanf("%d"z&m),m){mem_pos=0;

88node*root=create_tree(100z200z0z1000ztrue);while(m-){getchar();cmd=getchar();if(cmd==T){inth,ia,iljdoublea,I;scanf("%d%lf%吃&h,&a,&l);ia=10*(a+0.05);il=10*(1+0.05);update(rootzh,ia,il,true);}else{inthl,h2,ial,ia2;doubleal,a2;scanf("%d%d%lf%lf'z&hl,&h2,&al,&a2);ial=10*(al+0.05);ia2=10*(a2+0.05);if(hl>h2){swap(hlzh2);}if(ial>ia2){swap(ialzia2);}intt=query(rootzhl,h2zial,ia2ztrue);if(t==-l){puts("-l");}else{printf("%.llf

89"rt/10.0);}}}}14.稳定婚姻匹配*FunctionName:稳定婚姻匹配gale_shapley算法*Description:HDOJ1522MarriageisStable〃「mw[i][j]代表i男对女生的喜欢排名〃lwm[i][j]代表i女对j男的喜欢程度constintMAX=510;intw,m,n;intrmw[MAX][MAX];intImwfMAXlEMAX],lwm[MAX][MAX];intcouple[MAX];charsman[MAX][110],swoman[MAX][110];queueSQ;voidgale_shapley(){inti,man,woman;while(!SQ.empty()){SQ.popO;}memset(couple,-1/Sizeof(couple));for(i=l;i<=n;i++){SQ.push(i);)while(!SQ.empty()){man=SQ.front();for(i=l;i<=n;i++)lwm[woman][pre]){SQ.pop();SQ.push(pre);couple[woman]=man;break;}}}}}//while}15.后缀数组*FunctionName:后缀数组O(NLogN)*Description:PKU2774LongLongMessage#include#include

90usingnamespacestd;constintMAX=250000;chartxt[MAX];intmem[3][MAX]zc[MAX]zheight[MAX];int*SAz*nSA,*Rankz*nRank;intIenjl,l2;//O(NlogN)//SA[rank]=who;〃Suffix(SA[i])=0;i-){if(SA[i]>=k){nSA[-c[Rank[SA[i]-k]]]=SA[i]-k;}}for(i=len-k;i

91if(Rank[i]==len-1){height[Rank[i]]=k=0;}else{if(k>0){k=SA[Rank[i]+1];while(txt[i+k]==txt[j+k]){k++;}height[Rank[i]]=k;}}for(i=0zrs=0;i

92'\getlcpO);return0;}16.左偏树*FunctionName:左偏树*Description:HDOJ1512MonkeyKing*二叉堆的变形，方便堆的合并#include#include#include#includeusingnamespacestd;constintMAX=101000;structnode{intv,dis;〃键值,距离node*plz*pr;〃左右「树node*pf;〃父节点}mem[MAX];intmem_pos;intvalue[MAX]zn;node*new_node(){node*pt=mem+(mem_pos+4-);memset(pt,0zsizeof(node));returnpt;}〃清除节点休息inlinevoidclear(node*pos){if(pos==NULL)return;pos->pl=pos->pr=pos->pf=NULL;pos->dis=0;}〃合并堆O(logN)node*merge(node*paznode*pb){if(pa==NULL)returnpb;if(pb==NULL)returnpa;//maximumvertexheapif(pb->v>pa->v)std::swap(pa,pb);pa->pr=merge(pa->przpb);if(pa->pr)〈if(pa->pl==NULL11pa->pr->dis>pa->pl->dis){std::swap(pa->pl,pa->pr);}}if(pa->pr==NULL)pa->dis=O;elsepa->dis=pa->pr->dis+1;if(pa->pl)pa->pl->pf=pa;if(pa->pr)pa->pr->pf=pa;returnpa;}〃插入节点inlinenode*insert(node*root,node*val){returnmerge(rootzval);}〃删除最大顶inlinenode*delete_max(node*root){node*pt=root;

93root=merge(root->plzroot->pr);if(root)root->pf=NULL;clear(pt);returnroot;}〃取得最大值inlineintget_max(node*root){returnroot->v;}〃构建左偏树O(N)inlinenode*make_leftist_tree(){queuevnode*>SQ;node*ptempjinti;ptemp=new_node();for(i=0;iv=value[i];SQ.push(ptemp);}while(!SQ.empty()){intI=SQ.size();if(l==1)returnSQ.front();while(l—){node*pa=SQ.front();SQ.pop();node*pb=SQ.front();SQ.pop();SQ.push(merge(pazpb));}}}〃删除已知任意点O(logN)inlinevoiddelete_any(node*pos){node*ppre=pos->pf;node*pnew=delete_max(pos);if(pnew)pnew->pf=ppre;if(ppre){if(ppre->pl==pos)ppre->pl=pnew;elseppre->pr=pnew;}while(ppre){intvl="lzvr=-1;if(ppre->pl)vl=ppre->pl->dis;if(ppre->pr)vr=ppre->pr->dis;if(vlpl,ppre->pr);if(vr+1==ppre->dis)return;ppre->dis=vr+l;pnew=ppre;ppre=ppre->pf;}}nodeltree[MAX];intmain(){intij;intmzt;while(scanf(n%dMz&n)==l){for(i=0;ipf)pa=pa->pf;while(pb->pf)pb=pb->pf;if(pa==pb)puts(n-ln);else{node*pl=delete_max(pa);node*p2=delete_max(pb);pa->v/=2;pb->v/=2;pl=insert(pl,pa);pl=insert(plzpb);pl=merge(plzp2);printf("%d

94"zget_max(pl));}}}}17.标准RMQ-ST*FunctionName:标准RMQ-ST*Description:PKU3264BalancedLineup#include#include

95#includeusingnamespacestd;constintMAX=51000;constintLOGMAX=16;intnzq;intst_max[LOGMAX][MAX],st_min[LOGMAX][MAX];voidmake_st(){inti,j,k;for(j=l;(l<0){returnmax(st_max[k][a]zst_max[k][b-(l<

96',/rmq(a-l,b-lzl)-rmq(a-l,b-lz-l));}}}18.度限制最小生成树*FunctionName:度限制最小生成树*Description:PKU1639PicnicPlanning*有一个顶点有度限制，如果所有点都有限制，当限制>4时是NP#include#include#include#include#include

97//mst:度限制生成树vectormst[MAX];queuesq;〃最小花费，park下标，限制度数intcost,park,deg;//O(NlogN)prime求所有连通分量mstvoidprime_all_mst(){intij;priority_queuepq;nodenow,next;memset(viszO,sizeof(vis));for(i=0;i<=n;i++)mst[i].clear();vis[park]=true;block[park]=1;bs=l;〃park为第个连通分量cost=0;for(i=l;i<=n;i++){if(!vis[i]){bs++;while(!pq.empty())pq.pop();now.s=i;now.t=i;now.dis=0;pq.push(now);while(!pq.empty()){now=pq.top();pq.pop();if(vis[now.t])continue;vis[now.t]=true;mst[now.s].push_back(now.t);mst[now.t].push_back(now.s);block[now.t]=bs;cost+=now.disjnext.s=now.t;for(j=l;j<=n;j++){if(!vis[j]&&path[next.s][j]!=-1){next.t=j;next.dis=path[next.s][j];pq.push(next);}}}}}}//O(N)park连接各连通分量boolconnect_block(){inti,j,k;〃选取连接相邻连通分量的最小边for(i=2;i<=bs;i++)v0min[i][0]=INT_MAX;while(!sq.empty())sq.pop();for(i=l;i<=n;i++){if(path[park][i]!=-1&&v0min[block[i]][0]>path[park][i]){v0min[block[i]][0]=path[park][i];vOmin[block[i]][l]=i;}}k=0;for(i=2;i<=bs;i++){if(v0min[i][0]!=INT_MAX){cost+=v0min[i][0];path[park][v0min[i][l]]=-l;dmax[v0min[i][l]]=INT_MIN;sq.push(vOmin[i][l]);〃用来初始化dmaxk++;〃能连通的分量数}}〃图连通，且限制度数大于等于连通分量数deg-=bs-1;returnk>=bs-1&°>=0;}//0(N)计算dmaxvoidcal_dmax(){inti;memset(visz0,sizeof(vis));while(!sq.empty()){intnow=sq.front();sq.pop();vis[now]=true;for(i=0;isq2;memset(visz0,sizeof(vis));sq2.push(pos);vis[pos]=true;

98while(!sq2.empty()){intnow=sq2.front();sq2.pop();for(i=0;ipath[park][j]-dmax[j]){minv=path[park][j]-dmax[j];minp=j;}}}v=cost+minv;if(minp==-111v>=cost)returnfalse;cost=v;path[park][minp]=-1;〃差额最小添加删除操作del_path(minpzdmax[minp]);mst[park].push_back(minp);while(!sq.empty())sq.pop();sq.push(minp);dmax[minp]=INT_MIN;cal_dmax();}for(i=0;i

99",cost);}19.最优比率生成树*FunctionName:最优比率生成树(迭代法)*Description:PKU2728DesertKing#include#include#include#includeusingnamespacestd;constintMAX=1100;intn;structpoint{intxzyzz;}vi[MAX];structnode{intszt;doubledis;booloperator<(constnode&tt)const{returndis>tt.dis;}};doubledist[MAX][MAX];boolvis[MAX];doublerate;

100doubleprime(){doublecost=0;doublelen=Ojdoubled[MAX]zv;intpre[MAX];intij;memset(visz0zsizeof(vis));vis[0]=true;for(i=l;id[j]){minv=d[j];minp=j;}}vis[minp]=true;cost+=abs(vi[pre[minp]].z-vi[minp].z);len+=dist[pre[minp]][minp];for(j=l;j(v=abs(vi[minp].z-vi[j].z)-rate*dist[minp][j])){d[j]=v;pre[j]=minp;}}}returncost/len;}intmain(){intij;while(scanf("%dnz&n),n){for(i=0;i

101nzrate);}}19.最小花费置换//CowSorting〃对一个轮换进行处理的时候，应该考虑在轮换内进行交换，或与轮换外的元素交换之后，使代价值更小#include#include#includeusingnamespacestd;intg[10100]zn;boolvis[10100];intpos[101000];structnode(intvzp;booloperator<(constnode&t)const{returnv

102vis[tpos]=true;tpos=pos[g2[tpos].v];len++;}while(tpos!=i);〃选择两种方案中的最优方案sum+=min((len-2)*tminz(len+l)*mmin+tmin);}}printf("%d

103"，sum);}}19.区间K大数//POJ2104#include#include#include#includeusingnamespacestd;constintNMAX=100000;constintLOGNMAX=174-1;intsortseq[LOGNMAX][NMAX];intnum[NMAX];structnode{intl,rzd;node*pl,*pr;}mem[(NMAX<<1)+100];intmemposznzm;node*root;node*make_tree(intIJntr,intd){node*rt=mem+(mempos++);rt->l=I;rt->r=r;rt->d=d;if(I==r){sortseq[d][l]=num[l];retumrt;}intmid=(l+r)>>l;rt->pl=make_tree(lzmidzd+l);rt->pr=make_t「ee(mid+l,「,d+l);inti=l,j=mid+l,k=l;while(i<=mid&&j<=r){if(sortseq[d+l][i]l&&rt->r<=t){if(val<=sortseq[rt->d][rt->l])return0;elseif(sortseq[rt->d][rt->r]r-rt->l+1;elseif(sortseq[rt->d][rt->r]==val)returnrt->r-rt->l;intI=rt->l,r=rt->rzmid;while(I<=r){mid=(l+r)>>1;if(val<=sortseq[rt->d][mid])r=mid-1;elseI=mid+1;}returnI-rt->l;}else{ret=0;mid=(rt->l+rt->r)>>1;if(s<=mid)ret+=query(rt->plzval);if(mid+1<=t)ret+=query(rt->przval);returnret;}}//二分查找时遇到相同值的处理非常重要intmain()

104for(i=0;i>1;//二分查找so「tseq[0][mid]在区间回t]中的排名intpos=query(rootzsortseq[0][mid]);if(rank

105”,sortseq[0][「]);}}22.LCA-RMQ-ST//POJ3417//onlineO(nlogn)-O(l)#include#include#include#includeusingnamespacestd;typedef_int64bigintjconstintMAX=100010;constintSTMAX=200010;constintLOGMAX=18;intnzm;constintENDFLAG=0;structEDGELIST{intstart[MAX];intlast[MAX];intedge[MAX<<1][2];//poszlistnextinttot;voidclear(){tot=ENDFLAG+1;memset(last,ENDFLAG,sizeof(last));memset(start,ENDFLAG,sizeof(start));}voidpush_back(intsjntt){edge[tot][0]=t;edge[tot][l]=ENDFLAG;if(last[s]!=ENDFLAG){edge[last[s]][1]=tot;}else{start[s]=tot;}last[s]=tot;tot++;//swapif(s==t)return;edge[tot][0]=s;edge[tot][l]=ENDFLAG;if(last[t]!=ENDFLAG){edge[last[t]][1]=tot;}else{start[t]=tot;}last[t]=tot;tot++；}}tree;intcov[MAX];boolvis[MAX];bigintcnt[2];introot[MAX]zson[MAX];intstn;intst_min[LOGMAX][STMAX];intorder[STMAX]zfirst[MAX]zdeep[STMAX];voidmake_st(){inti,j,k;for(i=0;i

106if(deep[ret]>deep[st_min[k][b-(l<y)swap(x#y);returnorder[rmq(x,y)];}intordcnt;intsq[MAX];intqf,qe;voiddfs(intposjntd){intij;vis[pos]=true;first[pos]=ordcnt;deep[ordcnt]=d;order[ordcnt++]=pos;for(i=tree.start[pos];i!=ENDFLAG;i=tree.edge[i][l]){intnext=tree.edge[i][0];if(vis[next])continue;son[pos]++;root[next]=pos;dfs(next,d+l);deep[ordcnt]=d;order[ordcnt++]=pos;}if(son[pos]==0)sq[qe++]=pos;}voidtreedp(){son[0]=-1;while(qf'9'11ch<'0');do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');returnret;}intmain(){inti,j,a,b,rt;n=get_val();m=get_val();if(n==1){puts("OM);return0;}tree,tot=ENDFLAG+l;qf=qe=0;for(i=0;i

107"/cnt[0]*m+cnt[l]);}22.LCA-larjan//POJ3417//offlineO(na(n))#include#include#include#includeusingnamespacestd;typedef_int64bigint;constintMAX=100010;intnzm;constintENDFLAG=0;structEDGELIST{intstart[MAX];intlast[MAX];intedge[MAX<

108memset(lastzENDFLAGzsizeof(last));memset(startzENDFLAGzsizeof(start));}voidpush_back(intsjntt){edge[tot][0]=t;edge[tot][l]=ENDFLAG;if(last[s]!=ENDFLAG){edge[last[s]][1]=tot;}else{start[s]=tot;}last[s]=tot;tot++;//swapif(s==t)return;edge[tot][0]=s;edge[tot][l]=ENDFLAG;if(last[t]!=ENDFLAG){edge[last[t]][1]=tot;}else{start[t]=tot;}last[t]=tot;tot++;}}tree,newed;intcov[MAX];boolvis[MAX];bigintcnt[2];intfather[MAX];intancestor[MAX];intfind_set(intx){if(father[x]==x)returnx;returnfather[x]=find_set(father[x]);}voidunion_set(intxjnty){father]find_set(y)]=x;}voidtarjan(intposjntpre){intij;father[pos]=pos;ancestor[pos]=pos;for(i=tree.start[pos];i!=ENDFLAG;i=tree.edge[i][l]){intnext=tree.edge[i][O];if(next==pre)continue;tarjan(nextzpos);union_set(posznext);cov[pos]+=cov[next];>vis[pos]=true;for(j=newed.start[pos];j!=ENDFLAG;j=newed.edge[j][l]){intnext=newed.edge[j][O];if(vis[next])cov[ancestor[find_set(next)]]-=2;}if(covfpos]<=1)cnt[covfpos]]++;}intget_val(){intret=0;charch;while((ch=getchar())>'9'11ch<'0');do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');returnret;}intmain(){inti,j,a,b,rt;n=get_val();m=get_val();if(n==1)

109",cnt[0]*m+cnt[l]);}22.指数型母函数/*HDOJ1521排列组合有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。v=m,nv=10数量较少时，直接用除法*/#include#include#defineMAX100doublecal[2][MAX];double*prez*nowz*pt;intnzm;inta[ll];doublefac[100];

110intmain(){intij,kzsum;fac[0]=fac[l]=1;for(i=2;i<=20;i++){fac[i]=fac[i-l]*i;}while(scanf("%d%d"z&nz&m)==2){memset(cal,Ozsizeof(cal));for(i=0;i0){for(k=0;k<=a[i];k++){now[k+j]+=pre[j]/fac[k];}}}pt=now;now=pre;pre=pt;memset(nowz0,sizeof(cal[0]));pre[0]=1;}printf(,,%.OIf

111",fac[m]*pre[m]);}}22.指数型母函数(大数据)#includeusingnamespacestd;intmm[1000][100];_int64a[1000],b[1000];inline_int64gcd(—int64x,_int64y)〃求公约数{_int64temp;while(x%y){temp=x%y;x=y;y=temp;}returny;}intmain(){intnzm,i,j,k;—int64tmp,tmpl;while(scanf("%d%d",&nz&m)!=EOF){for(i=0;iy){tmp*=w;tmpl*=x;z=gcd(tmp,tmpl);if(z>1){tmp/=z;tmpl/=z;}w--;x—;}b[j+mm[i][k]]+=tmp*a[j];}}for(j=0;j<=m;j++)a[j]+=b[j];}printf("%I64d

112Hza[m]);}return0;}

11326.单词前缀树(字典树+KMP)constintNMAX=10000;constintLMAX=1000001;constintMMAX=51;constintMEMMAX=500000;chars[LMAX];charp[MMAX];intnzm;structNODE{intnsuffix;charchword;NODE*next,*father;NODE*son[26];}mem[MEMMAX];inttotal;NODE*root;NODE*new_node(){NODE*ret=&mem[total++];memset(retz0zsizeof(NODE));returnret;}//O(nMMAX)voidinsert(NODE*rtzchar*p){//puts(p);if(*p==0){rt->nsuffix++;retum;}if(rt->son[*p-'a']==NULL){rt->son[*p-*a*]=new_node();rt->son[*p-'a']->father=rt;rt->son[*p-,a']->chword=*p;}insert(rt->son[*p-'a'],p+1);}//0(nMMAX)voidbfs(){inti,j;queuesq;sq.push(root);while(!sq.empty()){NODE*now=sq.front();sq.pop();if(now->father==root)now->next=root;else{NODE*shift=(now->father)->next;while(shift!=root&&shift->son[now->chword-*a']==NULL)shift=shift->next;now->next=shift->son[now->chword-'a'];if(now->next==NULL)now->next=root;}for(i=0;i<26;i++){if(now->son[i]!=NULL)sq.push(now->son[i]);}}}//O(LMAX)intsolve(){intij;intret=0;NODE*now=root;NODE*psuffix;root->father=root;bfs();for(i=0;s[i];i++){while(now!=root&&now->son[s[i]-*a*]==NULL)now=now->next;now=now->son[s[i]-'a'];if(now==NULL)now=root;//addsamesuffixpsuffix=now;while(psuffix!=root&&psuffix->nsuffix!=-1){ret+=psuffix->nsuffix;psuffix->nsuffix=-1;psuffix=psuffix->next;}}returnret;}

11426.FFT(大数乘法)constintBASE=100000;constintN_DIGIT=5;constintN=32768;constdoublePI=acos(-l.O);structComplex{doublereal,imag;};Complexomega[N>>l];Complexa[N];Complexb[N];chars[1000003];intd[N]zlen;voidbitReverse(Complexa[]){inti,j=1,k;Complext;for(i=1;i>1;while(k>=1;}j+=k;})voidcalOmega(){doubleunit=2*PI/lenjintn=len>>1;for(inti=0;i>l;intm,k,j;intupzt,step;intilzi2;Complextmp;if(inverse){for(j=0;j>1,t=len>>s;//2A(log2(n)-s)!=n-2As!!!!!!!for(k=0;k

115memset(dz0,sizeof(int)*dLen);while(i=s){if(pLeft0&&d[i]==0;-i);sprintf(formatzN_DIGIT);printf("%d"rd[i]);for(—i;I>=0;—i)printf(format,d[i]);printf(H

116");}intmain(){while(init()){fft(a);fft(b);mul();fft(a,true);print();}return0;}26.二分图网络最大流最小割//PKU2125DestroyingTheGraph//二分图最小点权覆盖集，求割集//L设置一个集合A,最开始A={s},按如下方法不断扩张A://2,若存在一条边(u,v),其流量小于容量，且u属于A,则v加入A//3.若存在(v,u),其流量大于0,且u属于A,则v加入A

117〃4.A计算完毕，设B=V・A,最小割集£={(11*)|ugAzvgB}//CharactermeansthatBobremovesallarcsincomingintothespecifiedvertexandthatBobremovesallarcsoutgoingfromthespecifiedvertex.boolS[MAX];voiddfs(intpos){inti;S[pos]=1;for(i=l;i<=m;i++){if(!S[i]&&net[pos][i])dfs(i);}}structnode{intnum;charsign;}cs[MAX];voidfind_cut()

118"zi-1);cs[ps].num=i-l;cs[ps].sign=*-f;ps++；}}for(i=n+2;i<=2*n+l;i++){if(S[i]&&net[i][m]==0){//printf("%d+

119”，i-n-1);cs[ps].num=i-n-l;cs[ps].sign='+*;ps++;}}printf(n%d

120"zps);for(i=0;i

121"zcs[i].numzcs[i].sign);//puts("——")；〃for(i=l;iv=m;i++)if(S[i])printf("%d",i);//puts("

122——");}intwin[MAX],wout[MAX];intmain(){inti,j;while(scanf(H%d%d”，&n,&m)==2){memset(net,0,sizeof(net));for(i=2;i<=n+l;i++)scanf("%d"，win+i);for(i=2;i<=n+l;i++)scanf("%d",wout+i);while(m-){intx,y;scanf("%d%d"，&x,&y);x++;y+=n+l;net[x][y]=INT,MAX;}for(i=2;iv=n+l;i++){net[l][i]=wout[i];}for(i=n+2;i<=2*n+l;i++){net[i][2*n+2]=win[i-n];}m=2*n+2;printf("%d

123',/Edmonds_Karp());find_cut();}}26.混合图欧拉回路//1637PKUboolsolve(){inti,j;for(i=2;i0)net[i][m]+=x[i]>>1;elseif(x[i]<0)net[l][i]+=(-x[i])>>1;}intcap=0;for(i=2;i

124intflow=Edmonds_Karp();//whenflow==cap,sayitexisteulercircuit//printtheundirectededge'sdirection/*for(i=2;i%d

125",return(flow==cap);}intmain(){inti,j,cas;scanf("%d"z&cas);while(cas-){memset(indeg,0,sizeof(indeg));memset(outdeg,0,sizeof(outdeg));memset(net,0,sizeof(net));scanf("%d%d",&m,&s);for(i=0;iyindeg[y]++;outdeg[x]++;if(d==0)net[x][y]++;}n=m+2;puts(solve()?"possible":"impossible");}}26.无源汇上下界网络流/*2314ZJUReactorCooling*无源汇上下界网络流*(1)新建S,T*(2)D(u)=2B(i,u)-ZB(u,i)*D(u)>0,建弧(S,u),权值为D(u)*D(u)<0,建弧(u,T),权值为-D(u)*(3)求最大流，判定是否满流*/structNODE{intx,y;intb,c;NODE(int_x=0,int_y=0,int_b=0,int_c=0):x(_x),y(_y),b(_b),c(_c){}};vectornodes;intmake_net(){inti,j;intD[NMAX]={0};memset(net,0,sizeof(net));n+=2;vector:iteratoriter;foreach(iter,nodes){i=iter->x;j=iter->y;net[i][j]=iter->c-iter->b;D[j]+=iter->b;D[i]-=iter->b;}intret=0;for(i=2;i0)net[l][i]=D[i];elseif(D[i]<0)net[i][n]=-D[i];ret+=net[l][i];}returnret;}voidsolve()

126{inti,j;intcap=make_net();intflow=Edmonds_Karp();if(flow!=cap)puts(nNO

127");else{puts("YES");vector"iteratoriter;foreach(iter,nodes)printf("%d

128",iter->c-net[iter->x][iter->y]);}}intmain(){inti,j,cas;scanf("%d"A&cas);while(cas-){scanf(u%d%d",&n,&m);nodes.clear();for(i=0;i#includeconstintMOD=9973;boolA[32000];intprim[3500]zT[10][10];inttotal,n,m;voidinit(){inti,j;total=0;for(i=2;i<32000;i++)if(!A[i]){prim[total++]=i;for(j=2*i;j<32000;j+=i)A[j]=true;}}intphi(intx){inttemp,i,num;if(x==1)returnl;temp=1;for(i=0;i

129{temp*=num-l;temp%=MOD;x/=num;while(x%num==0){x/=num;temp*=num;temp%=MOD;}if(x==1)break;}}if(x!=l){temp*=x-l;temp%=MOD;}returntemp;}voidGT(intTT[][10]zintp){inti,j,sum,k;if(p==1){for(i=0;i

130while(k—)

131"zgn());}return0;}31.三分法求函数波峰//linle专场考研路茫茫一一早起看书constintMMAX=11000;constdoubleEPS=le-4;intx[MMAX]zy[MMAX];intnzm;#definef(dt)k*(dt-x[p-l])+y[p-l]+1.0*n/dt/dt;doubletriple_search(intp){doublemmin=le99;doublek=1.0*(y[p]-y[p-l])/(x[p]-x[p-l]);doublexl=x[p-l],xr=x[p];doublelmzrmzflmzfrm;while(fabs(xr-xl)>EPS){Im=(2.0*xl+xr)/3.0;rm=(2.0*xr+xl)/3.0;flm=f(lm);frm=f(rm);if(frm>flm)xr=rmzmmin=min(mminzflm);elsexl=Im,mmin=min(mminzfrm);}returnmmin;}doublesolve(){inti,j,kjdoublemmin=le99;for(i=l;i

132"zsolve。);}}32.单词计数，矩阵乘法//linle专场考研路茫茫一一单词情结//由正则表达式构造NFA,NFA转DFA,最小化DFA//构造状态转移矩阵，矩阵乘法typedefunsignedlonglongULL;#defineforeach(it,c)for(it=(c).begin();it!=(c).end();it++)#defineforsize(it,c)for(it=0;it<(c).size();it++)constintNMAX=6;intn,l;charrt[NMAX][6];constintSMAX=80;#defineADD(a,x)((a)=((a)+(x)))structMATRIX{ULLmat[SMAX][SMAX];intn;MATRIX(int_n=SMAX){n=_n;memset(mat,0zsizeof(mat));}voidto_E(intnn){inti;n=nn;memset(matz0zsizeof(mat));for(i=0;i

133for(i=0;in);while(ex>1){if(ex&l)tmp=tmp*ret;ret=ret*ret;ex>>=1;}ret=ret*tmp;returnret;}};constintNFAMAX=60;structEDGE{charch;intnext;EDGE(char_c=0,int_n=0):ch(_c),next(_n){}};vectornfa[NFAMAX];vectordfa[NFAMAX];vectormindfa[NFAMAX];intnfact;intdfasn;intmindfasn;vectordfactjvectormindfact;#defineBADD(xzp)((x)|=((ULL)l<<(p)))#defineBSUB(x,p)((x)&=~((ULL)l<<(p)))#defineBGET(xzp)((x)&((ULL)l«(p)))voidmake_nfa(){inti,j,k;for(i=0;ivis;ULLe_closure(intnow){int\,j;ULLret=0;vector:iteratoriter;BADD(retznow);if(vis[now])returnret;vis[now]=true;foreach(iter,nfa[now])if(iter->ch=='$,)ret|=e_closure(iter->next);returnret;}ULLe_closure2(ULLnow){inti,j;ULLret=now;vis.reset();for(i=0;ihash;voiddfs(ULLnow)

134{inti,j;vector:iteratoriter;vector::iteratoriter2;vectornxt[30];for(i=0;ich=='$')continue;nxt[iter->ch-,a'].push_back(iter->next);}}}intstag=hash[now];for(i='a';i<='z*;i++){if(nxt[i」a'].empty())continue;ULLnext=0;foreach(iter2,nxUi-'a'])BADD(next,*iter2);next=e_closure2(next);boolflag=falsejintntag=hash[next];if(ntag==0)ntag=hash[next]=dfasn++,flag=true;dfa[stag-l].push_back(EDGE(i,ntag-l));if(flag){if(BGET(nextznfact-l))dfact.push_back(ntag-l);dfs(next);}}}voidnfa_dfa(){inti,j,k;dfasn=l;vis.reset();hash.clear();dfact.clear();for(i=0;i>split;vector::iteratoriter;intbelg[NFAMAX];for(i=0;inewi;newi.push_back(i);split.push_back(newi);belg[i]=i;}boolflag=true;while(flag){flag=false;for(i=0;i>ibel,jbel;for(k=0;kch,belg[iter->next]));for(k=0;kchzbelg[iter->next]));sort(ibel.begin()zibel.end());sort(jbel.begin(),jbel,end());if(ibel==jbel){flag=truejbreak;}}if(flag)break;}if(flag){intsi=belg[split[i][0]]zs2=belg[split[j][O]];for(k=0;k

135if(belg[k]==s2)belg[k]=si;split[i].insert(split[i].end()zsplit[j].begin()zsplit[j].end());split.erase(split.begin()+j);}}for(i=0;iacts;for(i=0;ich-'a']=belg[iter->next];>for(j='a';j<='z';j++)if(gofj-'a']!=・l)mindfa[i].push_back(EDGE(j,go[j」a']));if(flag)mindfact.push_back(i);}}MATRIXT；MATRIXTT;MATRIXBT;MATRIXE;voidmake_matrix(){inti,j;vector:iteratoriter;E.to_E(mindfasn);T.n=mindfasn;memset(T.mat,0zsizeof(T.mat));for(i=0;inext]++;}BT.n=mindfasn<<1;memset(BT.mat,0,sizeof(BT.mat));BT.fill(Tz0,0);BT.fiH(E,0zmindfasn);BT.fill(Ezmindfasn,mindfasn);}ULLsolve(){inti,j;ULLret=0;vector::iteratoriter;make_nfa();nfa_dfa();dfasn=hash.size();min_dfa();make_matrix();BT=BTAl;TT.n=mindfasn;for(i=0;i

136",solve。);}}31.字符串和数值hash//整数hash//大素数104729,224737,611953,1299709,2015177constintMOD=20023;boolbhash[MOD];intvhash[MOD];intcnt[MOD];boolfind_hash(int&pos){intval=pos;pos%=MOD;

137for(;bhash[pos];pos=(pos+l)%MOD){if(vhash[pos]==val)returntrue;}returnfalse;}intmake_hash(intval){intpos=val;if(!find_hash(pos)){bhash[pos]=true;vhash[pos]=val;cnt[pos]=0;}cnt[pos]++;returnpos;}〃字符串hashconstintMOD=20023;boolbhash[MOD];charvhash[MOD][45];charstr[45];intcal_str(){inti,j,pos;for(i=pos=OJ=l;str[i];i4-+J=(j*27)8dNT_MAXzpos&=INT_MAX){intnum=str[i]-'a';if(str[i]=='')num=26;pos+=j*num;}returnpos%MOD;}boolfind_hash(int&pos){pos=cal_str();for(;bhash[pos];pos=(pos+1)%MOD){if(strcmp(vhash[pos]zstr)==0)returntrue;}returnfalse;}intmake_hash(){intpos;if(!find_hash(pos)){bhashfpos]=true;strcpy(vhash[pos],str);}returnpos;}31.滚动队列，前向星表示法intque[2][2000];intqf[2]zqe[2]zqnow;#definepush_que(a)(que[qnow][qe[qnow]++]=(a))#definepop_que2(que[qnowAl][qf[qnowAl]++])#defineswitch_queqnow人=1;\qf[qnow]=qe[qnow]=0;#defineempty_que2(qf[qnowAl]>=qe[qnowAl])#definesize_que2(qe[qnowAl]-qf[qnowAl])/*前向星表示法空间O(E+N)存储所有边，并用链表来实现读取s为起点的有向边方便插入和遍历所有边,删除是0(E)*/constintENDFLAG=-1;structEDGELIST{intstart[NMAX];intlast[NMAX];intedge[MMAX][2];//posJistnextinttot;voidclear(){tot=ENDFLAG+1;memset(last,ENDFLAGzsizeof(last));}voidpush_back(intsjntt){edge[tot][0]=t;edge[tot][l]=ENDFLAG;if(last[s]!=ENDFLAG)edge[last[s]][1]=tot;elsestart[s]=tot;last[s]=tot;tot++;}intget_start(ints){returnstart[s];}intget_next(int&p){p=edge[p][l];returnedge[p][O];}voiderase(ints,intt){inti,pre=ENDFLAG;intpzv;for(p=start[s];p!=ENDFLAG;p=edge[p][l]){v=edge[p][0];if(v==t){

138if(pre==ENDFLAG)start[s]=edge[p][l];elseedge[pre][l]=edge[p][l];}elsepre=p;}last[s]=pre;}};31.最小点基，最小权点基//HDOJ1827SummerHolidayvoidGabow(){intiJJ;//dfsinoriginalgraphmemset(idz0,sizeof(id));memset(visz0,sizeof(vis));see=step=l;order_pos=order2_pos=0;for(i=l;i<=n;i++)cost[i]?cost[i]:sel[id[i]];}}min_cost=0;for(i=l;i<=scc;i++){if(sel[i]!=-1){min_cost+=sel[i];}}min_num=scc+m;}intmain()

139n,min_numzmin_cost);}}