acm常用函数1

《acm常用函数1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案并查集voidUFset()//初始化{for(inti=0;i=0;s=parent[s]);while(s!=x)//优化方案―压缩路径，使后续的查找操作加速{inttmp=parent[x];parent[x]=s;x=tmp;}returns;}//R1和R

2、2是两个元素，属于两个不同的集合，现在合并这两个集合voidUnion(intR1,intR2){//r1为R1的根结点，r2为R2的根结点intr1=Find(R1),r2=Find(R2);inttmp=parent[r1]+parent[r2];//两个集合结点个数之和(负数)//如果R2所在树结点个数>R1所在树结点个数//注意parent[r1]和parent[r2]都是负数if(parent[r1]>parent[r2])//优化方案――加权法则{parent[r1]=r2;//将根结点r

3、1所在的树作为r2的子树(合并)parent[r2]=tmp;//更新根结点r2的parent[]值}else{parent[r2]=r1;//将根结点r2所在的树作为r1的子树(合并)parent[r1]=tmp;//更新根结点r1的parent[]值}}字符串的kmp算法：#include#include#include#include#include#includeusingnamespacest

4、d;//ifstreamfin("g.txt");精彩文档实用标准文案//ofstreamfout("g.out");chars[1000];charp[1000];intnext[1000];intn,m;//长度voidnext_val(){inti,j;j=-1;i=0;next[0]=-1;while(i

5、

6、p[i]==p[j]){i++;j++;if(p[i]!=p[j])next[i]=j;elsenext[i]=next[j];}elsej=next[j];}

7、}intindex(){inti,j;i=0;j=-1;while(i

8、

9、p[j]==s[i]){i++;j++;}elsej=next[j];}if(j>m-1)returni-m+1;elsereturn0;精彩文档实用标准文案}intmain(){freopen("g.txt","r",stdin);inti;cin>>n;cin>>s;//主串cin>>m;cin>>p;//模式串next_val();for(i=0;i

10、]+1;}cout<>n;inti,j,k;for(i=1;i<=n;i++){for(j=1;j<=n;j++)cin>>m[i][j];cin>>b[i];}for(i=1;i

11、i+1;j<=n;j++)if(m[j][i]!=0){精彩文档实用标准文案for(k=1;k<=n;k++){doublet=m[i][k];m[i][k]=m[j][k];m[j][k]=t;}doublet;t=b[i];b[i]=b[j];b[j]=t;}}if(m[i][i]==0)continue;都为0就下也回合，for(k=i+1;k<=n;k++){if(m[k][i]==0)continue;for(j=i+1;j<=n;j++){m[k][j]-=(m[i][j]/m[i][i]

12、)*m[k][i];}b[k]-=(b[i]/m[i][i])*m[k][i];m[k][i]=0;}}//回带过程if(m[n][n]!=0)x[n]=b[n]/m[n][n];elseif(b[n]==0)x[n]=0;else{cout<<"NOSolution!"<=1;i--){for(j=n;j>i;j--){x[i]-=x[j]*m[i][j];}if(m[i][i]!=0)x[i]=(