学习acm算法模板集

ACM二.重要与定FibonacciLucasCatalanStirlingNumber(SecondBellStirling'sSumofReciprocalYoungGreatestCommonDivisorSievePrimeModuleInverseExtendedEuclidModularLinearEquation模线性方程(同余方程EulerFunction单源最短路径(Bellman-ford算法单源最短路径(Dijkstra算法路稳定匹LCA-RMQ-LCA–指数型母函数（大数据单词前缀树（字典树带约束的轨道计数(Burnside引理LCSubsequence一.常用函数#includeintgetchar(void //一个字符,一般用来去掉无用字char*gets(char*str //一行字符#includevoid*mallocsize_tsize //动态内存分配,开辟大小为sizevoidqsort(void*buf,size_tnum,size_tsize,int(*compare)(constvoid*constvoid*)); Saintcompare_ints(constvoid*a,constvoid*b{int*arg1=(int*)a; int*arg2=(int*)b;if(*arg1<*arg2)return-1;elseif(*arg1==*arg2)return0;elsereturn1;}intarray[]={-2,99,0,-743,2,3,4}; intarray_size=7;qsort(array,array_size,sizeof(int),compare_ints);#include//求反正弦arg-11返回值-pi/2pi/2]doubleasin(doublearg);//求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值-1,1]doublesin(doublearg);//eargdoubleexp(doublearg//num的对数,基数为edoublelogdoublenum//numdoublesqrt(doublenum//base的expdoublepow(doublebase,doubleexp#include<string.//初始化内存,void*memset(void*buffer,intch,size_tcount);memset(the_array,0,sizeof(the_array));//printf是它的变形,intsprintf(char*buffer,constchar*format,...);sprintf(s,"%d%d",123,4567);//s=" //scanf是它的变形,intsscanf(constchar*buffer,constchar*format,...);Sample:charresult[100]="24 o",str[100]; intnum;sprintf(result,"%d%s",num,str);//num=24;str="hello";//字符串比较,返回值<0代表str1<str2,=0代表str1=str2,>0代表str1>str2intstrcmp(constchar*str1,constchar*str2);[标准container概要vector<T 大小可变的向量,类似数组的用法, 队列,empty(),front(),pop(),stack<T> 栈,empty(),top(),pop(),push()priority_queue<T> 优先队列,empty(),top(),pop(),push()set<T> 关联数组,常用来作hash[标准algorithm摘录for_eac 对每一个元素都唤起（调用） 用新的值替换元素,O(N) （拷贝）元素,O(N)re 排序,O(N 合并有序的序列,[C++String摘录 e 第二章重要与定Fibonacci0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610F0FiFi11

n

5 Lucas

1,3,4,7,11,18,29,47,76,15n 5Ln Catalan1,2,5,14,42,132,429,1430,4862,16796,58786,

C(2n,n将n+2边形沿弦切割成nn=n=n+1个数相乘,n= (1(23)),((12)n= (1(2(3 (1((23)4)) ((12)(3 ((1(23))(((12)3)n个节点的不同形状的二叉树数(严《数据结构》从n*nn=2;n=3;StirlingNumber(Secondnm个无标号的盒子中,要求无一为空,其不同0(m0||nSSn,mS

(nm

C(m,i)(mSpecialSn,0

1(3n32n3)Sn,nBellnnnBnStirling'sn!

n eSumofReciprocalEulerGamma= 1ln(n) (ni1YoungYoungTableau(杨式图表)是一个矩阵它满足条件:如果格子[i,j]没有元素,则[i+1,j]也一定没有元素如果格子[i,j]a[i,j],则[i+1j]要么没有元素,a[i+1ja[i,j]Y2

(nn=nk份且每份不能为空,for(intp=1;p<=n;p++)for(inti=p;i<=n;i++)for(intj=k;j>=1;j--dp[i][j]+=dp[i-p][j-1];cout<<dp[n][k]<<endl;dp[i][j]=dp[i-k][j-1];dp[i][j]=dp[i-k][j-1];(k=1..m)D2pab2r abRpabcdsan%b((((a%b)*nnpn1pn2pnm,n (n11)(n21)(nm第三章大数模板typedefint//应不大于以防乘法时溢出constintBase=1000;constintCapacity=struct{intintData[Capacity];xnum():Len(0)xnum(constxnum&V):Len(V.Len)memcpy(Data,V.Data,Len*sizeof}xnum(intV):Len(0)for(;V>0;V/=Base)Data[Len++]=V%}xnum(charxnum&operator=(constxnum&{Len=memcpy(Data,V.Data,Len*sizeof*Data);return*this;}int&operator[](intIndex){returnData[Index];intoperator[](intIndex)const{returnData[Index];voidfor(inti=Len-2;i>=0;i--)for(intj=Base/10;j>0;j/=10)}xnum::xnum(char{intI,Data[Len=0]=J=for(I=strlen(S)-1;I>=0;I--)Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=}if(Data[Len]>0)}intcompare(constxnum&A,constxnum&{intif(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)returnreturnA[I]>B[I]?1:-}xnumoperator+(constxnum&A,constxnum&{xnumR;intI;intCarry=for(I=0;I<A.Len||I<B.Len||Carry>0;{if(I<A.Len)Carry+=A[I];if(I<B.Len)Carry+=B[I];R[I]=Carry%Base;Carry/=}R.Len=return}xnumoperator-(constxnum&A,constxnum&{xnumintCarry=0;R.Len=A.Len;intI;for(I=0;I<R.Len;{R[I]=A[I]-if(I<B.Len)R[I]-=if(R[I]<0)Carry=1,R[I]+=Base;elseCarry=0;}while(R.Len>0&&R[R.Len-1]==0)R.Len--;returnR;}xnumoperator*(constxnum&A,constint{intif(B==0)return0;xnumR;hugeintCarry=for(I=0;I<A.Len||Carry>0;{if(I<A.Len)Carry+=hugeint(A[I])*B;R[I]=Carry%Base;Carry/=}R.Len=return}xnumoperator*(constxnum&A,constxnum&{intif(B.Len==0)return0;xnumR;for(I=0;I<A.Len;{hugeintCarry=for(intJ=0;J<B.Len||Carry>0;{if(J<B.Len)Carry+=hugeint(A[I])*B[J];if(I+J<R.Len)Carry+=R[I+J];if(I+J>=R.Len)R[R.Len++]=Carry%Base;elseR[I+J]=Carry%Base;Carry/=}}return}xnumoperator/(constxnum&A,constint{xnumR;intI;hugeintC=for(I=A.Len-1;I>=0;I--{C=C*Base+A[I];R[I]=C/B;C%=}R.Len=while(R.Len>0&&R[R.Len-1]==0)R.Len--;returnR;}xnumoperator/(constxnum&A,constxnum&{intxnumR,Carry=0;intLeft,Right,for(I=A.Len-1;I>=0;I--{Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/if(compare(B*Mid,Carry)<=0)Left=Mid;elseRight=Mid-1;}R[I]=Carry=Carry-B*}R.Len=while(R.Len>0&&R[R.Len-1]==0)R.Len--;returnR;}xnumoperator%(constxnum&A,constxnum&{intxnumR,Carry=0;intLeft,Right,for(I=A.Len-1;I>=0;I--{Carry=Carry*Base+Left=Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/if(compare(B*Mid,Carry)<=0)Left=Mid;elseRight=Mid-1;}R[I]=Carry=Carry-B*}R.Len=while(R.Len>0&&R[R.Len-1]==0)R.Len--;returnCarry;}istream&operator>>(istream&In,xnum&{charfor(V=0;In>>{V=V*10+(Ch-if(cin.peek()<='')brea}return}ostream&operator<<(ostream&Out,constxnum&{intOut<<(V.Len==0?0:V[V.Len-for(I=V.Len-2;I>=0;I--for(intJ=Base/10;J>0;J/=10)Out<<V[I]/J%10;return}xnumgcd(xnuma,xnum{if(compare(b,0)==0)returna;elsereturngcd(b,a%b);}intdiv(char*A,int{intintC=intAlen=strlefor(I=0;I<Alen;{C=C*Base+A[I]-'0';C%=B;}return}xnumC(intn,int{intxnumsum=for(i=n;i>=n-m+1;i--)sum=sum*i;for(i=1;i<=m;i++)sum=sum/i;return}#defineMAXN9999#defineDLEN4classBigNum{inta[1000];//可以控制大数的位数intlen;//大数长度BigNum(){len=1;memset(a,0,sizeof(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; operator%(constint &)const; operator>(constBigNum&voidBigNum::BigNum(constint{intc,d=b;len=0;while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+d=d/(MAXN+ a[len++]=}a[len++]=}BigNum::BigNum(const{intt,k,index,l,for(i=l-1;i>=0;i-{t=0;k=i-for(intj=k;j<=i;j++)a[index++]}}BigNum::BigNum(constBigNum&T):{inti;for(i=0;i<len;i++)a[i]=}BigNum&BigNum::operator=(constBigNum&{len=n.len;inti;for(i=0;i<len;i++)a[i]=n.a[i];return}BigNumBigNum::operator+(constBigNum&T)BigNumt(*this);inti,big;//位数big=T.len>len?T.len:len;for(i=0;i<big;i++){t.a[i]if(t.a[i]>{t.a[i+t.a[i]-}}if(t.a[big]!=0)t.len=big+1;elset.len=big;return}BigNumBigNum::operator-(constBigNum&T){inti,j,big;boolflag;BigNumt1,t2;if(*this>T){}else}for(i=0;i<big;{if(t1.a[i]<t2.a[i]){j=i+1;while(t1.a[j]==0)j++;while(j>i)t1.a[j--]+=t1.a[i]+=MAXN+1-}elset1.a[i]-=}t1.len=while(t1.a[len-1]==0&&t1.len>{t1.len--;big--;}returnt1;}BigNumBigNum::operator*(constBigNum&T)constBigNumret;inti,j,up;intfor(i=0;i<len;{up=for(j=0;j<T.len;j++)temp=a[i]*T.a[j]+ret.a[i+j]+up;if(temp>MAXN){temp1=temp-temp/(MAXN+1)*(MAXN+up=temp/(MAXN+1);ret.a[i+j]=temp1;}elseup=ret.a[i+j]=te}}if(up!=ret.a[i+j]=}ret.len=i+while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}BigNumBigNum::operator/(constint&b){BigNumret;inti,down=for(i=len-1;i>=0;i--)ret.a[i]=(a[i]+down*(MAXN+1))/down=a[i]+down*(MAXN+1)-ret.a[i]*}ret.len=while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}intBigNum::operator%(constint&b){intfor(i=len-1;i>=0;i--)d=((d*(MAXN+1))%b+a[i])%}return}BigNumBigNum::operator^(constint&n){BigNumif(n==0)return1;if(n==1)return*this;intm=n;while(m>1)inti;for(i=1;{}m-=i;}return}boolBigNum::operator>(constBigNum&T){intif(len>T.len)returntrue;elseif(len==T.len){ln=len-while(a[ln]==T.a[ln]&&ln>=0)ln--;if(ln>=0&&a[ln]>T.a[ln])returntrue;elsereturnfalse;}elsereturn}void{intcout<<a[len-for(i=len-2;i>=0;i--cout<<}}constintok=intget_val(int&{ret=0;charch;while((ch=getchar())>'9'||ch<'0');do{ret=ret*10+ch-}while((ch=getchar())<='9'&&ch>='0');returnok;}intget_val(int&{ret=0;charch;boolneg=while(((ch=getchar())>'9'||ch<'0')&&ch!='-');if(ch=='-'){neg=while((ch=getchar())>'9'||ch<'0')}doret=ret*10+ch-}while((ch=getchar())<='9'&&ch>='0');ret=(neg?-ret:ret);returno}//整数,可判EOF和EOLconstinteof=-1;constinteol=-2;intget_val(int&{ret=0;charch;while(((ch=getchar())>'9'||ch<'0')&&ch!=EOF);if(ch==EOF)returneof;doret=ret*10+ch-}while((ch=getchar())<='9'&&ch>='0');if(ch=='\n')returneol;return}//浮点intget_val(double&{ret=doublebase=0.1;charch;booldot=false,neg=while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');if(ch=='-'){neg=while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-')}doif(ch=={dot=true;}if(dot)ret+=(ch-'0')*base;base*=0.1;}elseret=ret*10+(ch-}while(((ch=getchar())<='9'&&ch>='0')||ch=='.');ret=(neg?-ret:ret);return}第四章数论算法GreatestCommonDivisor最大公约数int(intx,int{intwhile(y>{t=x%y;x=y;y=}return}Primeboolis_prime(int{if(u==0||u==1)returnfalse;if(u== returnif(u%2==0) returnfalse;for(inti=3;i<=sqrt(u);i+=2) returnfalse;returntrue;}SievePrime素数筛法constintM=1000;//M:boolmark[M];//true:primenumbervoidsieve_prime(){memset(mark,true,sizeof(mark));mark[0]=mark[1]=false;for(inti=2;i<=sqrt(M);i++){if(mark[i])for(intj=i*i;j<M;j+=i)mark[j]=false;}}}ModuleInverse模逆元//ax≡1(modn)intInv(inta,int{intd,x,d=extended_euclid(a,n,x,y);if(d==1) return(x%n+n)%n; return-1;//nosolution}ExtendedEuclid扩展算 (a,b)=d,则存在x,y,使d=ax+//extended_euclid(a,b)=ax+intextended_euclid(inta,intb,int&x,int{intif(b==0){x=1; y=0; returna;}d=extended_euclid(b,a%b,y,x);y-=a/b*x;returnd;} Equation模线性方程(同余方程//如果(a,b)不能整除c,则ax+by=c没有整数//ax≡b(modn)n>//上式等价于二元一次方程ax–ny=voidmodular_linear_equation(inta,intb,int{intd,x,y,x0,gc//可以减少扩展溢出的可gcd=(a,if(b%gcd!=0)cout<<"nosolution"<<endl;return;}a/=gcd;b/=gcd;n/=gcd;d=extended_euclid(a,n,x,y);if(b%d==0){x0=(x*(b/d))%n;//x0:basicintans=n;//minx=(x0%(n/d)+(n/d))%(n/d)for(inti=0;i<d;i++){ans=(x0+i*(n/d))%n;cout<<ans<<endl;}} cout<<"nosolution"<<}RemainderTheorem中国余数定理//x≡b[i](modw[i]),i∈[1,len-//前提条件w[i]>0,且w[]int_remainder(intb[],intw[],int{inti,d,x,y,m,n,ret;ret=0; n=1;for(i=0;i<len;i++) n*=w[i];for(i=0;i<len;i++){m=n/w[i]d=extended_euclid(w[i],m,x,y);ret=(ret+y*m*b[i])%n;}return(n+ret%n)%}//m≡r[i](moda[i]//a[i]//-1Pku2891StrangeWaytoExpress假设C≡A1(modB1)，C≡A2(modB2)令C=A1+X1B，那么X1B1≡A2-A1(modB2)。令B=lcm(B1,B2)，那么上面两条方程就可以被C’≡C(modB代替。LL{inti,if(n==returnLLm,x,x=modular_linear_equation(a[0],r[1]-r[0],a[1]);if(x==-1)return-m=x*a[0]+r[0];apre=LCM(a[0],a[1]);for(i=2;i<n;{x=modular_linear_equation(apre,r[i]-m,a[i]);if(x==-1)return-m=x*apre+apre=LCM(apre,}return}EulerFunction函数inteuler(intn){intans=1;inti;for(i=2;i*i<=n{if(n%i==0){n/=i;ans*=i-while(n%i=={n/=i;ans*=}}}if(n>1)ans*=n-}return}Farey//求MAX以内所有Farey的总数constintMAX= intn;boolnum[1100];//sqrt(MAX)intprime[1100],total;int64f[MAX],void{intmemset(num,false,sizeof(num));total=0;{if(!num[i])prime[total++]=i;j=i+i;while(j<1100){num[j]=true;j+=i;}}}}void{inti,j,inc[1]=1;{for(j=0;j<total;j++)if(i%prime[j]=={k=i/if(k%prime[j]==0)inc[i]=inc[k]*elseinc[i]=inc[k]*(prime[j]-1);break;}}if(j==total)inc[i]=i-}f[1]=for(i=2;i<MAX;i++)f[i]=f[i-1]+}intmain()while(scanf("%d",&n),n)printf("%I64d\n",}}Farey序列构造//构造5000以内的Farey序列constintMAX= inttotal;intintvoidmake_farey_seq(intx1,inty1,intx2,int{if(x1+x2>n||y1+y2>n)return;make_farey_seq(x1,y1,x1+x2,y1+y2);total++;farey[0][total]=x1+x2;farey[1][total]=make_farey_seq(x1+x2,y1+y2,x2,y}intma{intscanf("%d%d",&n,&t);total=1;farey[0][1]=farey[1][1]=farey[0][total+1]=farey[1][total+1]=1;total++;while(t--)scanf("%d",if(k>total)puts("Noelseprintf("%d/%d\n",farey[0][k],}}Miller_Rabbin素数测试，Pollard_rho因式分解 int64constchar*pformat="%I64d";I64big_rand(I64m){I64x=rand();x*=rand();if(x<0)x=-x;returnx%=}//x*y%I64mod_mul(I64x,I64y,I64{if(x==0||y==0)returnreturn(((x&1)*y)%n+(mod_mul(x>>1,y,n)<<1)%n)%}//x^y%I64mod_exp(I64x,I64y,I64{I64ret=1;while(y){if(y&1)ret=mod_mul(ret,x,n);x=mod_mul(x,x,n);y>>=}return}boolMiller_Rabbin(I64n){//O(times*(logN)^3)I64i,j,x,m,k;if(n==2)returnif(n<2||!(n&1))returnfalse;m=n-1;k=0;while(!(m&1))m>>=1,k++;//binaryscanfor(i=0;i<4;i++){//testtimesx=big_rand(n-2)+2;x=mod_exp(x,m,n);if(x==1)continue;for(j=0;j<k;j++){if(x==n-1)break;x=mod_mul(x,}if(j>=k)return}return/*lrjP.218for(i=0;i<20;i++){x=big_rand(n-2)if(mod_exp(x,n-1,n)!=1)return}return}I64(I64x,I64y)if(x>y)std::swap(x,y);while(x){I64t=y%x;y=x;x=}return}I64func(I64x,I64m)return(mod_mul(x,x,m)+1)%}I64Pollard(I64{if(Miller_Rabbin(n))returnn;if(!(n&1))return2;I64i,x,y,ret;i=1;while(true)x=iy=ret=gcd(y-x,n);while(ret==1){x=func(x,n);y=ret=gcd((y-x+n)%n,n)%}if(0<ret&&ret<n)return}}I64factor[100],nfac,minfac;voidcal_factor(I64n){I64x=Pollard(n);if(x==n){//factor[nfac++]=x;minfac=min(minfac,x);}}voidprint_factor(I64{I64nfac=0;std::sort(factor,factor+nfac);for(i=0;i<nfac;i++){if(i>0)putchar('}}constI64lim=100000;intmain(){I64n,t,i;srand((unsigned)time(NULL));while(t--)scanf(pformat,&n);if(Miller_Rabbin(n))puts("Prime");else{if(!(n&1))puts("2");else{for(minfac=3;minfac<lim&&n%minfac;minfac+=2);if(minfac>=lim){I64rn=sqrt(1.0*n);if(rn*rn==n){minfac=}elseminfac=n;}}}}}}第五章图论算法最小生成树(Kruscal算法/********************FunctionName 最小生成树(Kruscal算法Description ZJU1203Swordfish************************/#include<iostream>#include#include<cstdio>#include<cmath>usingnamespacestd;structstruct_edges{intbv,tv;//bv起点tvdoublew;//struct_edgesedges[10100边集structstruct_a{doublex;doublestruct_aintpoint[101n,e;//n顶点数e边数(注意是无向网络)doublesum;intkruscal_f1(intpoint[],int{inti=while(point[i]>0) i=point[i];returni;}boolUDlesser(struct_edgesa,struct_edges{returna.w<voidkruscal()//只需要准备好n，e，递增的边集edges[]{intfor(i=0;i<n;i++) i=j=0;while(j<n-1&&i<e)v1=kruscal_f1(point,edges[i].bv);v2=kruscal_f1(point,edges[i].tv);if(v1!=v2){sumedges[i].w注意sum0point[v1]=v2;}}intma{intk,i,j;while(n!={sum=0;for(i=0;i<n;i++)for(i=0;i<n;i++)//0for(j=i+1;j<n;j++)//{if(i==j)continue;edges[e].w=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-

sort(edges,edgeseUDlesser);//得到一个递增的边集，注意是从0printf("Cased:\nk);//cout<<"Casek<<":"<<endl;printf("Theminimaldistanceis:%.2f\n",sum);//输出sumif(n!=0)}}最小生成树(Prim算法/********************FunctionName 最小生成树(Prim算法Description ZJU1203SwordfishO(N^************************/#include<iostream>#include<cmath>#include<cstdio>usingnamespacestd;doublesum,arr_list[101][101],min;inti,j,k=0,n;struct{floatx;floatstruct_aarr_xy[101];structstruct_b{intpoint;floatlowcost;struct_bvoidprim(intn) //prim需要准备：narr_list[][]0开{inti,j,k;for(j=0;j<n{if(j!=k){closedge[j].point=k;closedge[j].lowcost=}}for(i=0;i<n;i++){ j<n;j++){if(closedge[j].lowcost!=0&&closedge[j].lowcost<{k=min=closedge[j].}}sum+= //不要改成 sum即为所求closedge[k].lowcost=0;for(j=0;j<n;j++){if(arr_list[k][j]<closedge[j].{closedge[j].point=k;closedge[j].lowcost=arr_list[k][j];}}}}arr_list[][]=WijVi,Vj 如果intma{while(n!={sum=0;for(i=0;i<nfor(i=0;i<n;i++)for(j=0;j<n;j++)//得到邻接矩阵arr_list[][]y[i].x-arr_xy[j].x)+(arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));cout<<"Caseprintf("Theminimaldistanceis:%.2f\n",sum); }}单源最短路径(Bellman- 算法structnodeintnode(inta=0,intb=:e(a),v(b)vector<vector<node>>path;intn,p,q;int SPFA(ShortestPathFasterbool{inti,j,k,now,l;nodenext;bitset< >vis;queue<int>SQ;memset(dist,-vis[1]=true;dist[1]=0;for(i=0;{l=SQ.size();if(l==0)break;while(l--){now=SQ.fvis[now]=false;for(j=path[now].size()-1;j>=0;j--{next=if(dist[next.e]==-1||dist[next.e]>dist[now]+next.v){dist[next.e]=dist[now]+next.v;if(!vis[next.e])vis[next.e]=true;}}}}}return}单源最短路径(Dijkstra算法/********************FunctionName 单源最短路径(Dijkstra算法Description 贪心,O(N^2),********************intmatrix[200][200],n; //matrix[][],30000表示无限大,即无边.否则为有边,voidDijkstra(intx,int //起点Vx终点{inti,j,k,path[40000],mark[40000];intmin,dist[40000];for(i=1;i<=n;i++){mark[i]=dist[i]=matrix[x][i];path[i]=x;}mark[x]=1;do{if(mark[i]==0&&{min=dist[i];k=i;}if(k)mark[k]=1;if(matrix[k][i]<30000&&{dist[i]=min+matrix[k][i];path[i]=k;}} //dist[y]的值就是从Vx到Vydo{cout<<k<<"<--";k=path[k];}全源最短路径(Folyd算法/********************FunctionName 全源最短路径(Folyd算法Description DP,O(N^********************voidFloyd(){intfor(k=0;k<ve{for(i=0;i<vertex_number;i++){for(j=0;j<vertex_number;j++){if((graph[i][k]==-1)||(graph[k][j]==- if((graph[i][j]==-1)||(graph[i][j]>{graph[i][j]=graph[i][k]+graph[k][j]; path[i][j]=k; }}}}}/********************FunctionName ******************** void{intboolp=true;while(p){{p=true;}if(f[i]==top) }}top--}网络中求最大流Edmonds_Karp最短增广路算法O(VE^参数含义 n代表网络点数,第0节点为源点,第n节点为汇返回值 最大流constintNMAX=210;intnet[NMAX][NMAX];intpath[NMAX],n;int{queue<int>SQ;intneck[NMAX],i;memset(path,-neck[0]=INT_MAX;while(!SQ.empty())intnow=SQ.front();if(now==n)break;for(i=1;i<=n;i++){if(net[now][i]>0&&path[i]==-{path[i]=neck[i]=min(neck[now],net[now][i]);SQ.push(i);}}}if(path[n]==-1)return-1;returnneck[n];}intEdmonds_Ka{intnow,intmax_flow=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;}}returnma}网络中求最大流HLPP高度标号预流推进算法O(V^2*E^参数含义 n代表网络点数,第0节点为源点,第n节点为汇earn代表各点的盈余high[]返回值 最大流constintNMAX=intearn[NMAX],net[NMAX][NMAX],high[NMAX];intn,m;queue<int>voidpush(intu,intv)intex=min(earn[u],net[u][v]);earn[u]-=ex;net[u][v]-=ex;earn[v]+=ex;net[v][u]+=ex;}voidrelable(intu)inti,mmin=INT_MAX;for(i=0;i<=n;i++){if(net[u][i]>0&&high[i]>=high[u])mmin=min(mmin,}}high[u]=mmin}voiddischarge(int{inti,vn;while(earn[u]>0){vn=for(i=0;i<=n&&earn[u]>{if(net[u][i]>0&&high[u]=={vn++;if(i!=n)SQ.}}if(vn==0)}}voidinit_preflow()intmemset(high,0,sizeof(high));memset(earn,0,sizeof(earn));while(!SQ.empty())SQ.pop();high[0]=n+1;for(i=1;i<=n;i++){if(net[0][i]>0)earn[i]=earn[0]-=net[i][0]=net[0][i];net[0][i]=0;if(i!=n)SQ.}}}int{inti,j;while(!SQ.empty()){intoverp=SQ.front();}return}网络中求最大流Dinic算法适用于稠密图，实际复杂度低于HLPP参数含义 n代表网络点数,第节点为源点,第n节点为汇dis[]代表从源点出发的距离标号path[]cur[]返回值 最大流constintNMAX=21000;constintMMAX=250000<<1;structEDGEintu,v,cap,flow;intnext;EDGE(int_u=0,int_v=0,int_c=0,int_f:u(_u),v(_v),cap(_c),flow(_f)constintENDFLAG=-1;structEDGELIST{intstart[NMAX];intlast[NMAX];inttot;EDGEarcvoidclear()tot=ENDFLAGmemset(last,ENDFLAG,}voidpush_back(EDGE{edge.next=ENDFLAG;arc[tot]=edge;if(last[edge.u]!=ENDFLAG)arc[last[edge.u]].next=elsestart[edge.u]=tot;last[edge.u]=tot;tot}//voidadd_arc(EDGE{push_back(EDGE(edge.v,edge.u,edge.c}intintqf[2],qe[2],#definepush_que(a)(que[qnow][qe[qnow]++]=(a))#definepop_que2 (que[qnow^1][qf[qnow^1]++])#defineswitch_queqnow^=1;\qf[qnow]=qe[qnow]=0;#defineempty_que2(qf[qnow^1]>=qe[qnow^1])#definesize_que2 (qe[qnow^1]-qf[qnow^1])intn,intintpath[NMAX],deep;intcur[NMAX];boolbfs()inti,dis[0]=0;qnow=while(!empty_que2)intl=size_que2;while(l--){intu=for(i=net.start[u];i!=ENDFLAG;i=net.arc{intv=net.arcif(dis[v]==-1&&net.arc[i].cap>net.arc{dis[v]=if(v==n)return}}}}return}int{inti,j;intu;intmaxflow=0;while(bfs()){memcpy(cur,net.start,sizeof(cur));for(deep=u=0;true;){if(u==n)intneck=INT_MAX,pos;for(i=0;i<deep;i++){intres=net.arc[path[i]].cap-net.arc[path[i]].flow;if(res<neck){neck=pos=}}maxflow+=for(i=0;i<deep;i++)net.arc[path[i]].flow+=neck;net.arc[path[i]^1].flow-=neck;}deep=u=}for(i=cur[u];i!=ENDFLAG;i=net.arc{if(net.arc[i].cap>net.arc&&dis[u]+1==dis[net.arc[i].v])brea}cur[u]=if(i!=ENDFLAG)path[deep++]=i;u=net.arc[i].v;}elseif(deep==0)break;dis[u]=-1;u=net.arc[path[--}}}return}/********************网络中最小费用最大流参数含义 n代表网络中的总节点数,第0节点为源点,第n节点为汇net代表剩余网络cost[][]代表单位费用算法:初始最小费用和最大流均为0在最短路中求出最大流，即为增广路，再修改剩余网络，直到无可增广路为止 最小费用，最大流量************************/constintNMAX=210;intnet[NMAX][NMAX],intpath[NMAX],ecost[NMAX];intn;boolbe{intfill(ecost,ecost+NMAX,INT_MAX);ecost[0]=0;boolflag=while(flag)flag=false;for(i=0;i<=n;i++){if(ecost[i]==INT_MAX)continuefor(j=0;j<=n;j++)if(net[i][j]>0&&ecost[i]+cost[i][j]<{flag=ecost[j]=ecost[i]+cost[i][j];path[j]=i;}}}}returnecost[n]!=}int{intintmincost=0,maxflow=0;while(bellman_ford()){intnow=intneck=INT_MAX;while(now!=0){intpre=neck=min(neck,net[pre][now]);now=pre;}maxflow+=neck;now=n;while(now!=0){intpre=path[now];net[pre][now]-=neck;net[now][pre]+=cost[now][pre]=-cost[pre][now];mincost+=cost[pre][now]*neck;now=pre;}}return}/********************网络中最小费用最大流 邻接表SPFA实参数含义 n代表网络中的总节点数,第s节点为源点,第t节点为汇ecost[] 最小费用，最大流********************//POJconstintNMAX=5100;//点数constintMMAX30000;//边数constintINF=0x7f7f7f7f;intpath[NMAX],ecost[NMAX];intn;ints,structEDGEintu,v,cap,cost,flow;intnext;EDGE(int_u=0,int_v=0,int_c=0,int_ct=0,int_f:u(_u),v(_v),cap(_c),flow(_f),cost(_ct)constintENDFLAG=-1;structEDGELIST{intstart[NMAX];intlast[NMAX];inttot;EDGEarcvoidclear()tot=ENDFLAGmemset(last,ENDFLAG,}voidpush_back(EDGE{edge.next=ENDFLAG;arc[tot]=edge;if(last[edge.u]!=ENDFLAG)arc[last[edge.u]].next=elsestart[edge.u]=tot;last[edge.u]=tot;tot}//voidadd_arc(EDGE{}intintqf[2],qe[2],#definepush_que(a)(que[qnow][qe[qnow]++]=(a))#definepop_que2 (que[qnow^1][qf[qnow^1]++])#defineswitch_queqnow^=1;\qf[qnow]=qe[qnow]=0;#defineempty_que2(qf[qnow^1]>=qe[qnow^1])#definesize_que2 (qe[qnow^1]-qf[qnow^1])bool{intbitset<NMAX>memset(ecost,0x7f,sizeof(ecost));memset(path,-1,sizeof(path));boolflag=true;qnow=1;vis[s]=1;ecost[s]=for(j=0;j<n&&flag;{flag=false;intl=size_que2;while(l--){intnow=pop_que2;vis[now]=0;for(i=net.start[now];i!=ENDFLAG;i=net.arc{EDGEed=if(ed.cap>ed.flow&&ecost[ed.v]>ecost[now]+ed.c{flag=ecost[ed.v]=ecost[now]+ed.cost;path[ed.v]=i;if(!{vis[ed.v]=1;}}}}}returnecost[t]!=}int{intintmincost=0,maxflow=0;while(SPFA()){intpre=path[t];intneck=INT_MAX;while(pre!=-1){intres=net.arc[pre].cap-net.arc[pre].flow;neck=min(neck,res);pre=path[net.arc}maxflow+=mincost+=ecost[t]*neck;pre=path[t];while(pre!=-1)net.arc[pre].flow+=neck;net.arc[pre^1].flow-=neck;net.arc[pre^1].cost=-net.arc[pre].cost;pre=path[net.arc[pre].u];}}return}函数接口 intRelabel_To_Front(ints,intd) s为源点，d为汇点返回值: 调用函数前的初始化工作:ver置为网络点的个数，c[i][j]代表节点i到节点j的流量，vl[i]存放i与相邻的所有节点constintVEX=405;//constintHMAX=810;//最大高度的定义,只要大于顶点的2intf[VEX][VEX];//intc[VEX][VEX];//边最大容量inth[VEX]; int int vector<int //邻接表，vl[i]存放与ivoidPushintu,intv)//u推向{intcf=c[u][v]- //u,vintd=e[u]<cf?e[u]:f[u][v]+=d;=-f[u][v];e[u]-=e[v]+=}voidRelabelintu)//u{inti,t,cinthmin=for(i=0;i<vl[u].size();i++){//寻找相邻最低点t=vl[u][i];cf=c[u][t]-if(cf>0&&h[u]<=h[t]&&h[t]<hmin)hmin=h[t];}h[u]=hmin+}voidInit_Preflow(ints)//初始化网络流，s{inti;inth[s]=ver;//for(i=0;i<vl[s].size();u=vl[s][i];f[s][u]=c[s][u];f[u][s]=-c[s][u];e[u]=c[s][u];e[s]-=}}voidDischarge(int{inti=0;intcf,v;if(vl[u].size()==0)return;while(e[u]>0){if(i<{v=cf=c[u][v]-}if(ivl[u].size()){Reli=}elseif(cf>0&&h[u]==h[v]+1)}}intRelabel_To_Front(ints,intd)//s为源点，d{intu,i,old_h;list<int>l;list<int>::itoriter;iter=for(i=0;i<veri++){if(i!=s&&i!=}iter=while(iterl.end()){u=*iter;old_h=h[u];if(h[u]>old_h){iter=l.begin();}}returne[ver-}/********************FunctionName Description PKU1419Graph团:指G的一个完全子图,最大独立集:最大团:************************/#include<cstdio>#include#defineNMAXboolpath[NMAX][NMAX];intn,mmax;intdp[NMAX];boolintseq[NMAX],//seqbooldfs(intpos,int{inti,j,unvis;booltv[NMAX];unvis=for{if(!v[i])unvis}}if(unvis==0){//|U|=0if(size>mmax){mmax=size;seq_pos=seq[seq_pos++]=pos+1;returntrue;}return}for(i=pos;i<n&&unvis>0{if(!v[i])if(unvis+size<=mmax||dp[i]+size<={return}v[i]=true;//U=U\{vi}unvis--;memcpy(tv,v,for(j=0;j<n;j++){//U∩N(vi);if(!path[i][j]){v[j]=}}if(dfs(i,size+1))seq[seq_pos++]=pos+1;returntrue;}memcpy(v,tv,}}//whileUisnotemptyreturnfalse;}int{inti,j;mmax=0;for(i=0;{path[i][i]=}for(i=n-1;i>=0;i--)for(j=0;j<n;j++){//Si∩N(vi);v[j]=!path[i][j];}dfs(i,dp[i]=mma}returnmma}intma{inti,j,x,y,e;intm,tn;scanf("%d",while(m--)scanf("%d%d",&n,&e);for(i=0;i<e;i++){scanf("%d%d",x--;y--path[x][y]=path[y][x]=}//maxindependentsetinoriginalgra//maxcliqueininversegraphfor(i=0;i<n;i++){for(j=0;{=}}memset(dp,0,sizeof(dp));printf("%d\n",max_clique());printf("%d",seq[0]);for(i=1;i<seq_pos;i++){printf("%d",}}}/********************FunctionName 最大二分图匹配(匈牙利算法Description HDOJ2063二分图:MN,MN匹配:一组边顶点分别在两个集合中,最大匹配:********************#include<cstdio>#include<memory>usingnamespacestd;constintMax=1100;vector<vector<int>>Bmap;intn,m,k,nm;intmark[Max];boolbooldfs(int{inti,pre,for(i=0;i<Bmap[pos].size(){tp=if(!flag[tp]{flag[tp]=true;pre=mark[tp];mark[tp]=pos;if(pre==-1||dfs(pre)) returntrue;mark[tp]=pre;}}return}inlineint{intmmax=0,i;for(i=1;i<=m;i++){memset(flag,0,sizeof(flag));if(dfs(i)) }returnmma}intma{