算法模板【最后更新2014-05】

KMP算法#include<cstdio>#include<cstring>#define N 20000char st1[N],st2[N],pre[N];int ans,len1,len2;void kmp1(){int i,j=0;for(i=2;i<=len1;i++){while(j&&st1[j+1]!=st1[i])j=pre[j];if(st1[j+1]==st1[i])j++;pre[i]=j;}}void kmp2(){int i,j=0;for(i=1;i<=len2;i++){while(j&&st1[j+1]!=st2[i])j=pre[j];if(st1[j+1]==st2[i])j++;if(j==len1)ans++,j=pre[j];}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%s",st1+1);len1=strlen(st1+1);scanf("%s",st2+1);len2=strlen(st2+1);kmp1();kmp2();printf("%d\n",ans);return 0;}trie#include<cstdio>#include<cstring>#define N 1000using namespace std;int n,i,len,ok,tot,trie[N][30];int flag[N];char s[100];void addtrie(int len){int x,i,ch;x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}if(flag[x]==1)ok=1;else ok=0;flag[x]=1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);tot=1;for(i=1;i<=n;i++){scanf("%s",s+1);len=strlen(s+1);addtrie(len);if(ok)printf("YES\n");else printf("NO\n");}return 0;}karp-rabin#include<cstdio>#include<cstring>#define M 1000000#define N 100000#define mo 10000int n,m,i,key[N],ha,w,len,ss,ans;char s[10000];int last[N],other[M],next[M];int jianyan(int x,int y){for(int i=0;i<n;i++)if(s[x+i]!=s[y+i])return 0;return 1;}int inhash(int ha,int wz){int w1;for(w1=last[ha];w1;w1=next[w1])if(jianyan(other[w1],wz))return 0;w++;next[w]=last[ha];last[ha]=w;other[w]=wz;return 1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);scanf("%s",s+1);len=strlen(s+1);for(i=1;i<=len;i++)key[i]=(key[i-1]*m+s[i])%mo;ss=1;for(i=1;i<=n;i++)ss=ss*m%mo;for(i=n;i<=len;i++){ha=((key[i]-key[i-n]*ss)%mo+mo)%mo;if(inhash(ha,i-n+1))ans++;}printf("%d\n",ans);return 0;}AC自动机#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 251000int test,n,tot,ans,i;int js[N],flag[N],g[N];int trie[N][26];char s[1001000];void addtrie(int len){int i,ch,x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}js[x]++;}void bfs(){int x,i,j,y;queue<int>q;q.push(1);while(q.size()){x=q.front();q.pop();for(i=0;i<26;i++){for(j=g[x];j;j=g[j])if(trie[j][i])break;if(y=trie[x][i])g[y]=j?trie[j][i]:1,q.push(y);else trie[x][i]=j?trie[j][i]:1;}}}void ac(int len){int i,ch,x=1,j;for(i=1;i<=len;i++){ch=s[i]-'a';x=trie[x][ch];for(j=x;j;j=g[j]){if(flag[j])break;ans+=js[j];flag[j]=1;}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%d",&n);tot=1;ans=0;memset(trie,0,sizeof(trie));memset(flag,0,sizeof(flag));memset(js,0,sizeof(js));memset(g,0,sizeof(g));for(i=1;i<=n;i++)scanf("%s",s+1),addtrie(strlen(s+1));bfs();scanf("%s",s+1);ac(strlen(s+1));printf("%d\n",ans);}return 0;}后缀数组#include<cstdio>#include<cstring>#define N 10000char s[N];int height[N],r[N],wa[N],wb[N],wc[N],wv[N],rank[N],sa[N];int test,i,ans,len;int cmp(int *y,int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++)wc[i]=0;for(i=0;i<n;i++)wc[x[i]=r[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<p;i++)wv[i]=x[y[i]];for(i=0;i<m;i++)wc[i]=0;for(i=0;i<p;i++)wc[wv[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(i=n-1;i>=0;i--)sa[--wc[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}}void calheight(int *r,int *sa,int n){int i,j,k=0;for(i=1;i<=n;i++)rank[sa[i]]=i;for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); }int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%s",s);len=strlen(s);s[len]='$';for(i=0;i<=len;i++)r[i]=s[i];da(r,sa,len+1,128);calheight(r,sa,len);ans=len*(1+len)/2;for(i=2;i<=len;i++)ans-=height[i];printf("%d\n",ans);}return 0;}spfa#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 10000#define M 100000struct edge{int n,o,j;}e[M];int n,m,i,x,y,z,w,j;int dist[N],flag[N],last[N];void add(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].j=z; }void spfa(int qi){int x,y,w1;queue<int>q;q.push(qi);memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(dist[x]+e[w1].j<dist[y]){dist[y]=dist[x]+e[w1].j;if(flag[y]==0)flag[y]=1,q.push(y);}}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);spfa(1);printf("%d\n",dist[n]);return 0;}folyd#include<cstdio>#include<cstring>#define max(x,y) x>y?x:y#define maxlongint 2147483647using namespace std;int f[101][101],max1,min1,i,j,k,m,n,x,y,w,ff[101];int main(){while(scanf("%d",&n)&&n!=0){memset(f,42,sizeof(f));for(i=1;i<=n;i++){f[i][i]=0;scanf("%d",&m);for(j=1;j<=m;j++)scanf("%d%d",&x,&y),f[i][x]=y;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];for(i=1;i<=n;i++){max1=0;for(j=1;j<=n;j++)max1=max(max1,f[i][j]);ff[i]=max1;}min1=maxlongint;for(i=1;i<=n;i++)if(ff[i]<min1)min1=ff[i],w=i;if(min1>100000000)puts("disjoint");else printf("%d %d\n",w,min1);}}folyd求最小环#include<cstdio>#include<cstring>#define oo 100000000#define min(x,y) ((x)<(y)?(x):(y))#define N 110int dist[N][N],edge[N][N],pre[N][N],a[N];int n,m,i,x,y,z,ans,ge,j;void extend_floyd(){int i,j,k,s1,st;for(k=1;k<=n;k++){for(i=1;i<k;i++)for(j=i+1;j<k;j++)if((s1=dist[i][j]+edge[j][k]+edge[k][i])<ans){ans=s1;st=j;ge=0;for(;st!=i;st=pre[i][st])a[++ge]=st;a[++ge]=i;a[++ge]=k;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if((s1=dist[i][k]+dist[k][j])<dist[i][j])dist[i][j]=s1,pre[i][j]=pre[k][j];}}int main(){freopen("delite2.in","r",stdin);freopen("delite2.out","w",stdout);scanf("%d%d",&n,&m);memset(dist,42,sizeof(dist));memset(edge,42,sizeof(edge));for(i=1;i<=n;i++)for(j=1;j<=n;j++)pre[i][j]=i;for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dist[x][y]=dist[y][x]=edge[x][y]=edge[y][x]=min(dist[x][y],z);}ans=oo;extend_floyd();if(ans>10000000)printf("-1\n");else for(i=1;i<=ge;i++)printf("%d%c",a[i],i<ge?' ':'\n');return 0;}堆优化dijkstra#include<cstdio>#include<cstring>#include<queue>using namespace std;#define maxn 110000#define maxm 500000#define CH getchar()typedef pair<int,int>pp;int last[maxn],dist[maxn],flag[maxn];int pre[maxm],other[maxm],ju[maxm];int n,m,home,noi,cmo,i,x,y,z,ans,w;inline int min(int x,int y){return x<y?x:y;}inline void read(int &x){char ch;for(ch=CH;ch<'0'||ch>'9';ch=CH);for(x=0;ch>='0'&&ch<='9';ch=CH)x=x*10+ch-48;}inline void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;}void dijkstra(int x){pp po;int p,point,w1;memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));priority_queue<pp,vector<pp>,greater<pp> >heap;heap.push(make_pair(0,x));while(heap.size()){po=heap.top();p=po.second;heap.pop();if(flag[p])continue;flag[p]=1;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];heap.push(make_pair(dist[point],point));}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d%d%d",&m,&n,&home,&noi,&cmo);for(i=1;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);dijkstra(noi);ans=dist[home]+dist[cmo];dijkstra(cmo);ans=min(ans,dist[home]+dist[noi]);printf("%d\n",ans);return 0;}K短路#include<cstdio>#include<queue>#include<cstring>using namespace std;#define maxn 1100#define maxm 11000struct rec{int p,l,g;};rec h[1000000];int last[maxn],flag[maxn],dist[maxn];int other[maxm],ju[maxm],pre[maxm],a[maxm],b[maxm],c[maxm];int n,m,k,i,x,y,w,r,p,l,w1,point;void swap(int &x,int &y){x=x+y;y=x-y;x=x-y;}void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} inline int heapcmp(rec a,rec b){return a.g>b.g;}void spfa(int x){int p,w1,point;queue<int>q;q.push(x);memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));flag[x]=1;while(q.size()){p=q.front();q.pop();flag[p]=0;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];if(!flag[point])flag[point]=1,q.push(point);}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);if(a[i]<b[i])swap(a[i],b[i]);add(b[i],a[i],c[i]);}spfa(1);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)add(a[i],b[i],c[i]);r=1;h[r].p=n;h[r].l=0;h[r].g=dist[n];while(r&&k){p=h[1].p;l=h[1].l;if(p==1)printf("%d\n",l),k--;pop_heap(h+1,h+r+1,heapcmp);r--;for(w1=last[p];w1;w1=pre[w1]){point=other[w1];r++;h[r].p=point;h[r].l=l+ju[w1];h[r].g=h[r].l+dist[point];push_heap(h+1,h+r+1,heapcmp);}}for(;k;k--)printf("-1\n");return 0;}拓扑排序#include<cstdio>#include<queue>using namespace std;#define N 100#define M 200int n,m,i,x,y,w1,w,p;int last[N],fb[N],ru[N];int next[M],other[M];queue<int>q;int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);w++;next[w]=last[x];last[x]=w;other[w]=y;ru[y]++;}for(i=1;i<=n;i++)if(ru[i]==0)q.push(i);while(q.size()){p=q.front();q.pop();printf("%d\n",p);for(w1=last[p];w1;w1=next[w1]){y=other[w1];ru[y]--;if(ru[y]==0)q.push(y);}}return 0;}匈牙利算法#include<cstdio>#include<cstring>using namespace std;#define N 1000#define M 10000struct edge{int n,o;}e[M];int n,m,i,x,y,w,ans;int last[N],flag[N],fa[N];void add(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}int xyl(int x){int w1;for(w1=last[x];w1;w1=e[w].n){y=e[w1].o;if(flag[y]==1)continue;flag[y]=1;if(fa[y]==0||xyl(fa[y])){fa[y]=x;return 1;}}return 0;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);for(i=1;i<=n;i++){memset(flag,0,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",ans);return 0;}最小路径覆盖#include<cstdio>#include<cstdlib>#include<cstring>#define maxn 300using namespace std;int test,w,ans,i,n,m,x,y,last[maxn],other[maxn],pre[maxn],fa[maxn];bool flag[maxn];bool xyl(int x){int point;for(int w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;}}}return false;}int main(){scanf("%d",&test);while(test--){scanf("%d",&n);scanf("%d",&m);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),w++,pre[w]=last[x],last[x]=w,other[w]=n+y;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}可重复最小路径覆盖#include<cstdio>#include<cstring>using namespace std;int n,m,i,j,k,ans,x,y,w,last[600],pre[300000],other[300000],fa[1200]; bool flag[1200],ff[600][600];bool xyl(int x){int w1,point;for(w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;} }}return false;}int main(){while(scanf("%d%d",&n,&m)&&(n||m)){memset(ff,false,sizeof(ff));for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ff[x][y]=true;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][k]&&ff[k][j])ff[i][j]=true;memset(last,0,sizeof(last));w=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][j])w++,pre[w]=last[i],last[i]=w,other[w]=j+n;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}最大流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 1000000#define N 10000#define M 100000struct edge{int n,o,v;}e[M];int n,m,w,S,T,ans,x,y,z,i;int d[N],last[N];;int min(int x,int y){return x<y?x:y;}void addflow(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;w++;e[w].n=last[y];last[y]=w;e[w].o=x;e[w].v=0; }int build(){int x,y,w1;queue<int>q;q.push(S);memset(d,0,sizeof(d));d[S]=1;while(q.size()){x=q.front();q.pop();for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(d[y]==0&&e[w1].v){d[y]=d[x]+1;q.push(y);if(y==T)return 1;}}}return 0;}int dinic(int x,int limit){int v,w1,y,flow;if(x==T)return limit;for(v=0,w1=last[x];w1&&v<limit;w1=e[w1].n){y=e[w1].o;if(d[y]==d[x]+1&&e[w1].v){flow=dinic(y,min(limit-v,e[w1].v));v+=flow;e[w1].v-=flow;e[w1^1].v+=flow;}}if(v==0)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;S=1;T=n;ans=0;for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),addflow(x,y,z);while(build())ans+=dinic(S,oo);printf("%d\n",ans);return 0;}费用流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 100000000#define N 10000#define M 100000struct edge{int n,o,v,f;}e[M];int n,m,i,x,y,z,money,ans,w,S,T;int dist[N],last[N],minf[N],flag[N],path[N];inline int min(int x,int y){return x<y?x:y;}void addfei(int x,int y,int z,int money){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;e[w].f=money; }int spfa(int qi){int x,y,w1;queue<int>q;memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;minf[qi]=oo;q.push(qi);while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n)if(e[w1].v>0){y=e[w1].o;if(dist[x]+e[w1].f<dist[y]){dist[y]=dist[x]+e[w1].f;minf[y]=min(minf[x],e[w1].v);path[y]=w1;if(flag[y]==0)flag[y]=1,q.push(y);}}}if(dist[T]>10000000)return 0;return 1;}void calcfei(){int x,y;ans+=dist[T]*minf[T];for(x=T;x!=S;){y=path[x];e[y].v-=minf[T];e[y^1].v+=minf[T];x=e[y^1].o;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;ans=0;for(i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&z,&money);addfei(x,y,z,money);addfei(y,x,0,-money);}S=1;T=n;while(spfa(S))calcfei();printf("%d\n",ans);return 0;}上下限网络流#include<cstdio>#include<cstring>#define min(x,y) (x)<(y)?(x):(y)#define maxn 300#define maxm 100000#define oo 1000000000struct edge1{int u;int v;int high;int low;};edge1 a[maxm];int last[maxn],d[maxn],q[maxn],f[maxn];int pre[maxm],other[maxm],rong[maxm],ans[maxm];int w,n,m,start,end,i,l,r,mid,maxflow,s1,now;void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;rong[w]=z;w++;pre[w]=last[y];last[y]=w;other[w]=x;rong[w]=0; }int build(){int l,r,p,w1,point;memset(d,0,sizeof(d));d[start]=1;l=0;r=1;q[1]=start;while(l!=r){l++;p=q[l];for(w1=last[p];w1;w1=pre[w1]){point=other[w1];if(!d[point]&&rong[w1]){d[point]=d[p]+1;if(point==end)return 1;r++;q[r]=point;}}}return 0;}int find(int x,int tot){int v,w1,point,s1;if(x==end)return tot;for(v=0,w1=last[x];v<tot&&w1;w1=pre[w1]){point=other[w1];if(d[point]==d[x]+1&&rong[w1]){s1=find(point,min(tot-v,rong[w1]));v+=s1;rong[w1]-=s1;rong[w1^1]+=s1;}}if(!v)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].high,&a[i].low);if(a[i].low)a[i].low=a[i].high;f[a[i].u]-=a[i].low;f[a[i].v]+=a[i].low;}a[m+1].u=n;a[m+1].v=1;start=n+1;end=start+1;l=-1;r=oo;while(l+1<r){mid=(l+r)/2;a[m+1].high=mid;a[m+1].low=0;memset(last,0,sizeof(last));w=1;maxflow=0;now=0;for(i=1;i<=m+1;i++)add(a[i].u,a[i].v,a[i].high-a[i].low);for(i=1;i<=n;i++)if(f[i]<0)add(i,end,-f[i]);else add(start,i,f[i]),maxflow+=f[i];while(build())while(1){s1=find(start,oo);if(!s1)break;now+=s1;}if(now==maxflow){r=mid;for(i=1;i<=m;i++)ans[i]=a[i].high-rong[i*2];}else l=mid;}if(r==oo){puts("Impossible");return 0;}printf("%d\n",r);for(i=1;i<m;i++)printf("%d ",ans[i]);printf("%d\n",ans[m]);}tarjan#include<cstdio>#define N 10000#define M 100000#define min(x,y) ((x)<(y)?(x):(y))int n,m,i,x,y,w,top,num,ss;int last[N],other[M],next[M],dfn[N],low[N],v[N],stack[N],team[N]; void addedge(int x,int y){w++;next[w]=last[x];last[x]=w;other[w]=y;} void tarjan(int x){int w1,y;dfn[x]=low[x]=++num;stack[++top]=x;v[x]=1;for(w1=last[x],y=other[w1];w1;w1=next[w1],y=other[w1])if(dfn[y]==0)tarjan(y),low[x]=min(low[x],low[y]);else if(v[y]==1)low[x]=min(low[x],dfn[y]);if(dfn[x]==low[x]){ss++;while(stack[top]!=x)y=stack[top],team[y]=ss,v[y]=0,top--;y=stack[top];team[y]=ss;v[y]=0;top--;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),addedge(x,y);for(i=1;i<=n;i++)if(dfn[i]==0)num=0,top=0,tarjan(i);for(i=1;i<=n;i++)printf("%d %d\n",i,team[i]);return 0;}凸包#include<cstdio>#include<algorithm>#include<cmath>using namespace std;#define sqr(x) ((x)*(x))#define N 10000#define eps 1e-8struct po{double x,y;}a[N],stack[N];int n,i,top;double ans;void swap(po x,po y){po z=x;x=y;y=z;}double chaji(double x,double y,double xx,double yy){return x*yy-xx*y;} double dis(po a,po b){return sqrt(sqr(b.x-a.x)+sqr(b.y-a.y));}double cross(po a,po b,po c){return chaji(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);}int sortcmp(po aa,po bb){double s=cross(a[1],aa,bb);if(fabs(s)>eps)return s>0;return dis(a[1],aa)>dis(a[1],bb);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);for(i=2;i<=n;i++)if(a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))swap(a[1],a[i]);sort(a+2,a+n+1,sortcmp);top=1;stack[1]=a[1];for(i=2;i<=n;i++){while(top>1&&cross(stack[top-1],stack[top],a[i])<0)top--;top++;stack[top]=a[i];}for(i=2;i<=top;i++)ans+=dis(stack[i-1],stack[i]);ans+=dis(stack[top],stack[1]);printf("%.2lf\n",ans);return 0;}lca#include<cstdio>#include<queue>using namespace std;#define N 10000#define M 100000queue<int>q;int n,m,i,j,x,y,z,w,w1,test;bool fb[N];int last[N],fa[N][21],shen[N],dist[N];int other[M],next[M],ju[M];void swap(int &x,int &y){int z;z=x;x=y;y=z;}void addedge(int x,int y,int z){w++;next[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} int lca(int x,int y){int cha,i;if(shen[x]>shen[y])swap(x,y);cha=shen[y]-shen[x];for(i=20;i>=0;i--)if(cha>=1<<i)y=fa[y][i],cha-=1<<i;if(x==y)return x;for(i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),addedge(x,y,z),addedge(y,x,z);q.push(1);fb[1]=1;while(q.size()){x=q.front();q.pop();for(w1=last[x];w1;w1=next[w1])if(!fb[y=other[w1]])fb[y]=1,fa[y][0]=x,shen[y]=shen[x]+1,dist[y]=dist[x]+ju[w1],q.push(y);}for(i=1;i<=20;i++)for(j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];scanf("%d",&test);while(test--){scanf("%d%d",&x,&y);z=lca(x,y);printf("%d\n",dist[x]+dist[y]-dist[z]*2);}return 0;}kruskal#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define M 100000#define N 10000struct arr{int x,y,z;}a[M];int n,m,i,x,y,fa1,fa2,sum;int fa[N];int sortcmp(arr a,arr b){return a.z<b.z;}int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);sort(a+1,a+m+1,sortcmp);for(i=1;i<=n;i++)fa[i]=i;for(i=1;i<=m;i++){x=a[i].x;y=a[i].y;fa1=getfa(x);fa2=getfa(y);if(fa1!=fa2)fa[fa1]=fa2,sum+=a[i].z;}printf("%d\n",sum);return 0;}线段树#include<cstdio>#define N 10000struct arr{int sum,jia;}t[N*4];int n,i,x,y,z,sum,test;int a[N];char s[10];void downdate(int w,int l,int r){int ss=t[w].jia,m=(l+r)/2;t[w].jia=0;t[w*2].jia+=ss;t[w*2].sum+=ss*(m-l+1);t[w*2+1].jia+=ss;t[w*2+1].sum+=ss*(r-m);}void update(int w){t[w].sum=t[w*2].sum+t[w*2+1].sum;} void buildtree(int w,int l,int r){int m;if(l==r){t[w].sum=a[l];return;}m=(l+r)>>1;buildtree(w*2,l,m);buildtree(w*2+1,m+1,r);update(w);}void modify(int w,int l,int r,int ll,int rr,int z){int m;if(l>=ll&&r<=rr){t[w].jia+=z;t[w].sum+=z*(r-l+1);return;}m=(l+r)>>1;downdate(w,l,r);if(ll<=m)modify(w*2,l,m,ll,rr,z);if(rr>m)modify(w*2+1,m+1,r,ll,rr,z);update(w);}void query(int w,int l,int r,int ll,int rr){int m;if(l>=ll&&r<=rr){sum+=t[w].sum;return;}downdate(w,l,r);m=(l+r)>>1;if(ll<=m)query(w*2,l,m,ll,rr);if(rr>m)query(w*2+1,m+1,r,ll,rr);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);buildtree(1,1,n);scanf("%d",&test);while(test--){scanf("%s",s);if(s[0]=='a')scanf("%d%d%d",&x,&y,&z),modify(1,1,n,x,y,z);if(s[0]=='q')scanf("%d%d",&x,&y),sum=0,query(1,1,n,x,y),printf("%d\n",sum);}return 0;}树状数组#include<cstdio>#define N 100000char s[10];int x,y,n,i,test;int a[N];void modify(int x,int y){for(;x<=n;x+=x&-x)a[x]+=y;}int query(int x){int sum=0;for(;x;x-=x&-x)sum+=a[x];return sum;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&x),modify(i,x);scanf("%d",&test);while(test--){scanf("%s%d%d",s,&x,&y);if(s[0]=='a')modify(x,y);if(s[0]=='q')printf("%d\n",query(y)-query(x-1));}return 0;}树链剖分#include<cstdio>#include<cstring>const int N=110000;const int M=220000;struct arr{int cc,sum;}t[N];struct edge{int n,o;}e[M];struct tree{int sum,ge,add;}c[N*4];int n,m,i,x,y,ans,jia,z,w;int team[N],path[N],rank[N],q[N],b[N],a[N],deep[N],fa[N],flag[N],last[N],sum[N]; char s[10];inline void addedge(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}inline void swap(int &x,int &y){int z=x;x=y;y=z;}void update(int w,int cc){c[w+cc].sum=c[w+w+cc].sum+c[w+w+1+cc].sum;c[w+cc].ge=c[w+w+cc].ge+c[w+w+1+cc].ge;}void build(int w,int l,int r,int cc){int mid;。

算法模板网络122王硕目录1.数学1.1 矩阵 (2)1.2 一次方程组的解 (3)1.3 矩阵的逆 (4)1.4 最大公约数 (6)1.5 欧几里得扩展 (6)1.6 素数表 (7)1.7 判断素数 (8)1.8 分解质因数 (9)1.9 欧拉函数 (10)1.10 欧拉函数表 (11)1.11 mobius函数 (12)1.12 数值积分 (12)1.13 数值积分（精确） (13)1.14 快速幂求余 (14)1.15 进制转换 (15)1.16 格雷码 (16)1.17 高精度类 (16)1.18 Fibonacci数列 (22)1.19 FFT (23)2.图论2.1 拓扑排序 (24)2.2 dijkstra (25)2.3 floyd-warshall (26)2.4 kruskal …………………263.序列3.1 快速排序 (28)3.2 逆序对 (28)3.3 最长不降子序列长度 (30)3.4 最长公共子序列长度 (31)3.5 最长公共上升子序列长度 (31)3.6 最长公共上升子序列 (32)4.字符串4.1 Sunday (34)4.2 子串清除 (34)4.3 KMP (37)5.数据结构5.1 并查集 (38)5.2 树状数组 (39)5.3 左偏树 (40)5.4 哈希 (41)5.5 RMQ线段树 (41)6.其他6.1 多边形面积 (43)6.2 幻方构造 (43)6.3 奇数阶次幻方 (45)1.1矩阵#include <iostream>#include <cstring>using namespace std;const int MAXN=100;const int MAXM=100;struct Matrix{int n,m;int a[MAXN][MAXM];void clear(){m=n=0;memset(a,0,sizeof(a));}Matrix operator +(const Matrix &b) const {Matrix tmp;tmp.n=n; tmp.m=m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)tmp.a[i][j]=a[i][j]+b.a[i][j];return tmp;}Matrix operator *(const Matrix &b) const {Matrix tmp;tmp.clear();tmp.n=n; tmp.m=m;for(int i=0;i<n;i++)for(int j=0;j<b.m;j++)for(int k=0;k<m;k++)tmp.a[i][j]+=a[i][k]*b.a[k][j];return tmp;}};1.2一次方程组的解#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#define MAX 10#define EPS 1e-8using namespace std;double a[MAX][MAX+1];bool l[MAX];double ans[MAX];void swap(double &x,double &y){double t;t=x;x=y;y=t;}inline int solve(double a[MAX][MAX+1],bool l[],double ans[],const int &n) {int res=0,r=0;int i,j,k;memset(ans,0,sizeof(a));memset(l,false,n);for(i=0;i<n;i++){for(j=r;j<n;j++)if(fabs(a[i][j])>EPS){for(k=i;k<=n;k++)swap(a[j][k],a[r][k]);break;}if(fabs(a[r][i])<EPS){res++;continue;}for(j=0;j<n;j++)if(j!=r&&fabs(a[j][i])>EPS){double tmp=a[j][i]/a[r][i];for(k=i;k<=n;k++)a[j][k]-=tmp*a[r][k];}l[i]=true;r++;}for(i=0;i<n;i++)if(l[i])for(j=0;j<n;j++)if(fabs(a[j][i])>EPS)ans[i]=a[j][n]/a[j][i];for(i=0;i<n;i++)if(fabs(ans[i])<EPS)ans[i]=0;return res;}int main(){int n;int i,j,res;cin>>n;for(i=0;i<n;i++)for(j=0;j<n+1;j++)cin>>a[i][j];res=solve(a,l,ans,n);for(i=0;i<n;i++)cout<<ans[i]<<" ";return 0;}1.3矩阵的逆#include <iostream>#include <vector>#include <cmath>#include <algorithm>#define MAX 10using namespace std;vector<double> a[MAX];vector<double> c[MAX];inline vector<double> operator *(vector<double> a,double b) {int i;int n=a.size();vector<double> res(n,0);res[i]=a[i]*b;return res;}inline vector<double> operator -(vector<double> a,vector<double> b) {int i;int n=a.size();vector<double> res(n,0);for(i=0;i<n;i++)res[i]=a[i]-b[i];return res;}inline void inverse(vector<double> a[],vector<double> c[],int n) {int i,j;for(i=0;i<n;i++)c[i]=vector<double> (n,0);for(i=0;i<n;i++)c[i][i]=1;for(i=0;i<n;i++){for(j=i;j<n;j++)if(fabs(a[j][i]>0)){swap(a[i],a[j]);swap(c[i],c[j]);break;}c[i]=c[i]*(1/a[i][i]);a[i]=a[i]*(1/a[i][i]);for(j=0;j<n;j++)if(j!=i&&fabs(a[j][i])>0){c[j]=c[j]-c[i]*a[j][i];a[j]=a[j]-a[i]*a[j][i];}}}int main(){int n,i,j;double x;cin>>n;for(j=0;j<n;j++){cin>>x;a[i].push_back(x);}inverse(a,c,n);for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<c[i][j]<<" ";cout<<endl;}return 0;}1.4最大公约数#include <stdio.h>int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int lcm(int a,int b){return a*b/gcd(a,b);}1.5欧几里得扩展#include <iostream>using namespace std;int gcd(int a,int b,int &x,int &y) {if(b==0){x=1;y=0;return a;}else{int r=gcd(b,a%b,y,x);y-=x*(a/b);return r;}}int main(){int a,b,x,y;scanf("%d%d",&a,&b);printf("%d ",gcd(a,b,x,y));printf("%d %d",x,y);return 0;}/*求AB的最大公约数，且求出X,Y使得AX+BY=gcd(A,B);15 205 -1 1*/1.6素数表#include <iostream>#include <cmath>#include <cstring>#define MAX 350000000using namespace std;bool valid[MAX];int prime[MAX];void getprime(int n,int &tot,int ans[]){int i,j;memset(valid,true,sizeof(valid));for(i=2;i<=n;i++){if(valid[i]){tot++;ans[tot]=i;}for(j=1;(j<=tot)&&(i*ans[j]<=n);j++){valid[i*ans[j]]=false;if(i%ans[j]==0)break;}}}int main(){int i,n,sum=0,j=0;cin>>n;getprime(n,sum,prime);for(i=1;i<=sum;i++){cout<<prime[i]<<" ";j++;if(j%10==0)cout<<endl;}return 0;}1.7判断素数#include <iostream>#include <cmath>using namespace std;long long int rsa(long long int a,long long int k,long long int m) {if(k==0)return 1%m;long long int tmp=rsa(a,k>>1,m);tmp=tmp*tmp%m;if(k&1)tmp=tmp*a%m;return tmp;}bool test(int n,int a,int d){if(n==2)return true;if(n==a)return true;if((n&1)==0)return false;while(!(d&1))d=d>>1;long long int t=rsa(a,d,n);while((d!=n-1)&&(t!=1)&&(t!=n-1)){t=t*t%n;d=d<<1;}return (t==n-1)||((d&1)==1);}bool isprime(int n){if(n<2)return false;int a[]={2,3,61,4567,23456789},i;for(i=0;i<5;i++)if(!test(n,a[i],n-1))return false;return true;}int main(){long long int i,n,sum=0;cin>>n;for(i=2;i<=n;i++)if(isprime(i)){cout<<i<<" ";sum++;if(sum%10==0)cout<<endl;}return 0;}1.8分解质因数#include <iostream>#include <cmath>#define MAX 10000long long int a[MAX],b[MAX],tot;using namespace std;void factor(long long int n,long long int a[],long long int b[],long long int &tot) {long long int temp=sqrt(n)+1,now=n;int i;tot=0;for(i=2;i<=temp;i++)if(now%i==0)a[++tot]=i;b[tot]=0;while(now%i==0){b[tot]++;now/=i;}temp=sqrt(now)+1;}if(now!=1){a[++tot]=now;b[tot]=1;}}int main(){long long int n,i;cin>>n;//fenjie(n,2);factor(n,a,b,tot);for(i=1;i<=tot;i++)cout<<a[i]<<" ";cout<<endl;for(i=1;i<=tot;i++)cout<<b[i]<<" ";return 0;}/*7212345678900630630*/1.9欧拉函数#include <stdio.h>long long int eular(long long int n) {long long int ret=1,i;for(i=2;i*i<=n;i++)if(n%i==0){n/=i,ret*=i-1;while(n%i==0)n/=i,ret*=i;}ret*=n-1;return ret;}int main(){long long int n;scanf("%lld",&n);printf("%lld",eular(n));return 0;}//小于或等于n的数中与n互质的数的个数。

一、粒子群算法粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法((Evolu2tionary Algorithm - EA）.PSO 算法属于进化算法的一种，和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover）和变异(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。

这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。

优化问题是工业设计中经常遇到的问题，许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题，人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点，二是要求有较高的收敛速度。

爬山法精度较高，但是易于陷入局部极小。

遗传算法属于进化算法(EvolutionaryAlgorithms）的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解。

遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码，找到最优解之后还需要对问题进行解码，另外三个算子的实现也有许多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。

1995年Eberhart 博士和kennedy博士提出了一种新的算法；粒子群优化（ParticalSwarmOptimization-PSO）算法。

这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。

粒子群优化(ParticalSwarmOptimization—PSO）算法是近年来发展起来的一种新的进化算法（Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种，和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质。

一、基本算法1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。

main(){int a,b,t;scanf("%d%d",&a,&b);printf("%d,%d\n",a,b);t=a; a=b; b=t;printf("%d,%d\n",a,b);}【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。

假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。

其中t为中间变量，起到“空杯子”的作用。

注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。

main(){int a,b,c,t;scanf("%d%d%d",&a,&b,&c);/*以下两个if语句使得a中存放的数最小*/if(a>b){ t=a; a=b; b=t; }if(a>c){ t=a; a=c; c=t; }/*以下if语句使得b中存放的数次小*/if(b>c) { t=b; b=c; c=t; }printf("%d,%d,%d\n",a,b,c);}2．累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。

“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。

例1、求1+2+3+……+100的和。

main(){int i,s;s=0; i=1;while(i<=100){s=s+i; /*累加式*/i=i+1; /*特殊的累加式*/}printf("1+2+3+...+100=%d\n",s);}【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。

常⽤算法模板开始存模板快速排序#include <cstdio>#include <algorithm>#include <iostream>using namespace std ;typedef long long ll ;const int maxN = 100010 ;int a[ maxN ] ;inline ll INPUT ( ) {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(x=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}void quick_sort ( const int l , const int r ) {if ( l > r ) {return ; ;}int i = l , j = r ;while ( i < j ) {while ( a[ j ] >= a[ l ] && j > i ) {--j ;}while ( a[ i ] <= a[ l ] && j > i ) {++i ;}if ( j > i )swap ( a[ i ] , a[ j ] ) ;}swap ( a[ l ] , a[ i ] ) ;quick_sort ( l , i - 1 ) ;quick_sort ( i + 1 , r ) ;}int main ( ) {int N = INPUT( ) ;for ( int i=1 ; i<=N ; ++i ) {a[ i ] = INPUT( ) ;}quick_sort ( 1 , N ) ;for ( int i=1 ; i<=N ; ++i ) {cout << a[ i ] << endl ;}return0 ;}View Code快速选择#include <cstdio>#include <algorithm>#include <iostream>using namespace std ;typedef long long ll ;const int maxN = 100010 ;int a[ maxN ] ;inline ll INPUT ( ) {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(x=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int quick_select ( const int l , const int r , const int K ) {int i = l , j = r ;while ( i < j ) {while ( a[ j ] >= a[ l ] && j > i ) {--j ;}while ( a[ i ] <= a[ l ] && j > i ) {++i ;}if ( j > i )swap ( a[ i ] , a[ j ] ) ;}swap ( a[ l ] , a[ i ] ) ;if ( i - l == K - 1 )return a[ i ] ;else if ( i - l >= K )return quick_select ( l , i - 1 , K ) ;elsereturn quick_select( i + 1 , r , K - ( i - l + 1 ) ) ;}int main ( ) {int N = INPUT ( ) ;int K = INPUT ( ) ;for ( int i=1 ; i<=N ; ++i ) {a[ i ] = INPUT( ) ;}cout << quick_select ( 1 , N , K ) << endl ;return0 ;}View Code树的重⼼//#include <bits/stdc++.h>#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;const int maxN = 20010 ;const int inf = 2147483647 ;struct Edge {int to , next ;}e[ maxN << 1 ] ;int head[ maxN ] , size[ maxN ] , hv[ maxN ] ;int _cnt ;int INPUT ( ) {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}void addEdge ( int x , int y ) {e[ ++_cnt ].to = y ;e[ _cnt ].next = head[ x ] ;head[ x ] = _cnt ;}void Dfs ( const int x , int fa ) {size[ x ] = 1 ;for ( int i=head[ x ] ; i ; i=e[ i ].next ) {if ( e[ i ].to != fa ) {Dfs ( e[ i ].to , x ) ;size[ x ] += size[ e[ i ].to ] ;}}for ( int i=head[ x ] ; i ; i=e[ i ].next ) {if ( e[ i ].to != fa && size[ e[ i ].to ] > size[ hv[ x ] ] ) {hv[ x ] = e[ i ].to ;}}}void init ( ){_cnt = 0 ;memset ( size , 0 , sizeof ( size ) ) ;memset ( hv , 0 , sizeof ( hv ) ) ;memset ( head , 0 , sizeof ( head ) ) ;}int main ( ) {for ( int T = INPUT ( ) ; T ; --T ) {init ( ) ;int N = INPUT ( ) ;for ( int i=1 ; i<N ; ++i ) {int x = INPUT ( ) , y = INPUT ( );addEdge ( x , y ) ;addEdge ( y , x ) ;}Dfs ( 1 , 1 ) ;int tmp , minNode = 0 , minval = inf ;for ( int i=1 ; i<=N ; ++i ) {int tmp = max ( size[ hv[ i ] ] , N - size[ i ] ) ;if ( tmp < minval ) {minval = tmp ;minNode = i ;}}printf ( "%d %d\n" , minNode , minval ) ;}return0 ;}poj1655Tire树#include <bits/stdc++.h>using namespace std ;const int maxN = 5010 ;typedef long long LL ;struct tireNode {int cnt ;bool last ;struct tireNode *next[ 26 ] ;tireNode ( ) {//构造⽅法初始化cnt = 0 ;last = false ;memset ( next , 0 , sizeof ( next ) ) ;}};char str_[ maxN ] ;void insert ( tireNode *root , char str[ ] ) {int len = strlen ( str + 1 ) ;tireNode *cur = root ;for ( int i=1 ; i<=len ; ++i ) {char ch = str[ i ] - 'a' ;if ( cur -> next[ ch ] == NULL ) {tireNode* newNode = new tireNode ;cur -> next[ ch ] = newNode ;}cur = cur -> next[ ch ] ;cur->cnt++ ;}cur -> last = true ;}bool find ( tireNode *root , char str[ ] ) {int len = strlen ( str + 1 ) ;tireNode *cur = root ;for ( int i=1 ; i<=len ; ++i ) {char ch = str[ i ] - 'a' ;if ( cur -> next[ ch ] == NULL ) return false ; cur = cur -> next[ ch ] ;}if ( cur -> last == true ) return true ;return false ;}int main ( ) {int N , M ;tireNode* root = new tireNode ;scanf ( "%d" , &N ) ;for ( int i=1 ; i<=N ; ++i ) {scanf ( "%s" , str_ + 1 ) ;insert ( root , str_ ) ;}scanf ( "%d" , &M ) ;for ( int i=1 ; i<=M ; ++i ) {scanf ( "%s" , str_ + 1 ) ;if ( find ( root , str_ ) ) printf ( "Yes\n" ) ;else printf ( "No\n" ) ;}return0 ;}动态字典树#include <bits/stdc++.h>using namespace std ;const int maxNode = 10010 ;typedef long long LL ;struct tireTree {static const int maxLen = 26 ;int tr[ maxNode ][ maxLen ] ;bool end[ maxNode ] ;int count[ maxNode ] ;int _cnt ;tireTree ( ) {_cnt = 1 ;memset ( tr , 0 , sizeof ( tr ) ) ;memset ( end , false , sizeof ( end ) ) ; }public :void insert ( char str[ ] ) {int cur = 1 , len = strlen ( str + 1 ) ;for ( int i=1 ; i<=len ; ++i ) {int idx = str[ i ] - 'a' ;if ( !tr[ cur ][ idx ] ) {tr[ cur ][ idx ] = ++_cnt ;}cur = tr[ cur ][ idx ] ;}end[ cur ] = true ;}public :bool exist ( char str[ ] ) {int cur = 1 , len = strlen ( str + 1 ) ;for ( int i=1 ; i<=len ; ++i ) {int idx = str[ i ] - 'a' ;if ( !tr[ cur ][ idx ] ) {return false ;}cur = tr[ cur ][ idx ] ;}return end[ cur ] ;}};tireTree tree ;char str[ 2000 ] ;int main ( ) {int N , M ;scanf ( "%d" , &N ) ;for ( int i=1 ; i<=N ; ++i ) {scanf ( "%s" , str + 1 ) ;tree.insert ( str ) ;}scanf ( "%d" , &M ) ;for ( int i=1 ; i<=M ; ++i ) {scanf ( "%s" , str + 1 ) ;if ( tree.exist ( str ) )printf ( "YES\n" ) ;elseprintf ( "NO\n" ) ;}return0 ;}静态字典树单调栈#include <iostream>#include <stack>#include <cstdio>using namespace std ;const int INF = 2147483647 ;class Element {private :int Val , Index ;public :Element ( ) {Val = 0 ;Index = -1 ;}Element ( const int __x , const int __y ) { Val = __x ;Index = __y ;}int getVal ( ) {return Val ;}int getIndex ( ) {return Index ;}void print ( ) {if ( Index == -1 ) cout << "Do not exist!!" << endl ;else cout << Index << "" << Val << endl ;}};stack <Element> stk ;int arr[ 100 ] ;Element Ans[ 100 ] ;int In ( ) {int x = 0 , f = 1 ; char ch = getchar ( ) ;while ( ch < '0' || ch > '9' ) { if ( ch == '-')f = -1 ; ch = getchar ( ) ;}while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ;} return x * f ;}int main ( ) {int N = In ( ) ;for ( int i=1 ; i<=N ; ++i ) arr[ i ] = In ( ) ;for ( int i=1 ; i<=N+1 ; ++i ) {Element ele ;if ( i != N+1 ) ele = Element ( arr[i] , i ) ;else ele = Element ( INF , -1 ) ;while ( !stk.empty ( ) && stk.top().getVal( ) < ele.getVal() ) {Ans[ stk.top().getIndex() ] = ele ;stk.pop ( ) ;}stk.push(ele) ;}for ( int i=1 ; i<=N ; ++i ) Ans[ i ].print ( ) ;return0 ;}View Code。

专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学1. 剩余定理2. N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7. 求N！的位数8.欧拉函数9. Miller-Rabin,大整数分解，求欧拉函数10. 第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14. Baby-step,giant-step n是素数.n任意15. a^b%c=a ^(b%eular(c)+eular(c)) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;//当前顶点数int best;//当前最大顶点数int vis[50];//当前解int bestn[50];//最优解int map[50][50];//临界表void dfs(int i){if(i>n){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map[105][105],in[105],vis[105],ans[105],n;int flag;void dfs(int step){if(flag) return ;if(step==n+1) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}int s,f;//起点和终点cin>>s>>f;//dijkstra 求最短路和次短路int flag[1005][2];int dis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(int c=0;c<2*n;c++) //找最短路和次短路，故要进行2*n次循环也可以改成while(1){int temp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(int j=1;j<=n;j++){if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;}if(temp==inf) break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(int l=0;l<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}else if(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}else if(d<dis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

核心算法——ACM模板一、贪心算法 (2)1、区间选点 (2)2、区间覆盖 (2)3、不相交区间 (2)4、哈夫曼编码 (2)5、最小值最大化、最大值最小化（二分查找） (2)二、动态规划 (5)1、最长公共子序列（LCS） (5)2、最长上升公共子序列（LIS） (7)3、子段和 (9)4、DAG上的动态规划 (13)5、区间DP (17)6、状态压缩DP (24)7、双线DP (30)8、背包问题(见背包九讲) (32)三、数据结构 (32)1、并查集 (32)2、树状数组 (34)3、（字符串）KMP匹配 (37)四、最小生成树算法 (41)Prime核心算法 (41)Kruskal算法 (44)五、单源最短路径 (50)Dijkstra核心算法 (50)Bellman_Ford算法 (54)SPFA算法（Bellman_Ford的队列实现） (58)六、二分图匹配 (61)1、匈牙利算法 (61)七、网络流 (63)1、SAP算法 (64)2、Dinic算法 (68)一、贪心算法1、区间问题区间选点选取尽量少的点覆盖所有的区间，是每个区间至少包含一个点。

对区间右端点进行排序。

区间覆盖选取尽量少的区间覆盖整个区域。

对左端点进行排序。

不相交区间选取尽量多的不相交区间。

对区间右端点进行排序。

2、哈夫曼编码3、最小值最大化、最大值最小化（二分查找）NYOJ 疯牛问题（最小值最大化）农夫John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。

为了不让牛互相伤害。

John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？#include#include#includeusing namespace std;int n, c;int pos[100005];bool judge(int k){int cnt = 1;int st = pos[0];for(int i = 1; i < n; ++i){if(pos[i] - st >= k){++cnt;if(cnt >= c)return true;st = pos[i];}}return false;}int Binary_search(int left, int right) /// 二分枚举满足条件的最大距离{while(left <= right){int mid = (left + right) >> 1;if(judge(mid)) /// 所求距离 >= mid，可以继续增大试探left = mid+1;else /// 所求距离 < mid,所以必须减小来试探right = mid-1;}return left-1;}int main(){while(~scanf("%d%d", &n, &c)){for(int i = 0; i < n; ++i)scanf("%d", &pos[i]);sort(pos, pos+n);printf("%d\n", Binary_search(0, pos[n-1] - pos[0]));}return 0;}NYOJ 摘枇杷（最大值最小化）理工学院的枇杷快熟了，ok，大家都懂得。

OI 算法模板1. 介绍OI（Olympiad in Informatics）是信息学奥林匹克竞赛的缩写，是一种选拔优秀计算机程序设计员的竞赛形式。

OI 算法模板是 OI 竞赛中常用的一些算法和数据结构的模板总结，可以帮助选手在竞赛中快速解决问题。

本文将介绍常见的 OI 算法模板，包括搜索算法、排序算法、图算法、动态规划等，以及一些常用的数据结构。

每个算法和数据结构都会给出详细的算法思想、实现方法和复杂度分析。

2. 搜索算法2.1 深度优先搜索（DFS）深度优先搜索是一种常见的搜索算法，通过递归或栈实现。

其基本思想是从起点出发，尽可能深地搜索每个可能的路径，直到找到目标或无法继续搜索为止。

def dfs(node):if node is None:return# 处理当前节点process(node)# 递归处理相邻节点for neighbor in node.neighbors:if neighbor not in visited:visited.add(neighbor)dfs(neighbor)时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。

2.2 广度优先搜索（BFS）广度优先搜索是一种常见的搜索算法，通过队列实现。

其基本思想是从起点出发，逐层地向外扩展，直到找到目标或无法继续扩展为止。

from collections import dequedef bfs(start):queue = deque([start])visited = set([start])while queue:node = queue.popleft()# 处理当前节点process(node)# 处理相邻节点for neighbor in node.neighbors:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。

算法模板数论：1、筛法素数产⽣器int findprime(int prime[],int n){int num,i,j,k,counter,*base,pown; n++; n/=2;pown=n*2;base=(int*)malloc(sizeof(int)*(n+1)*2); prime[0]=2;prime[1]=3;counter=2; for(i=1;i<=pown;i++)base[i]=0;for(i=3;i<=n;i+=3)for(j=0;j<2;j++){num=2*(i+j)-1;while(0==base[num]){prime[counter++]=num;for(k=num;k<=pown;k+=num){base[k]=1;}}}free(base);return counter;}数据结构1、中缀表达式转后缀表达式string str,suf;void translate();{ios::sync_with_stdio(false);co['+']=1,co['-']=1,co['*']=2,co['/']=2,co['%']=2;cin>>str;translate();cout<return 0;} void translate(){stacks;int size=str.size();for(register int i=0;i{if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')) suf.push_back(str[i]); else{if(s.empty()||(co[str[i]]>co[s.top ()])) s.push(str[i]);else{while(!s.empty()&&(co[s.top ()]>=co[str[i]])){suf.push_back(s.top());s.pop();}s.push(str[i]);}}}while(!s.empty()){s.pop();}}STL应⽤1、map: find() 找到返回指针，否则返回.end();Count()找到返回⼤于零的整数，否组返回0 mymap.insert ( pair('a',100) ); mymap['a']="an element";2、stringsize_t found;found=str.find(str2);if (found!=string::npos)图的遍历（深搜，⼴搜）深搜1、⽆路可逃？bool matrix[maxn][maxn]={0};bool tag[maxn][maxn]={0};int mx[]={0,1,0,-1};int my[]={-1,0,1,0};int t,n,m,sx,sy,tx,ty;int tempx,tempy;bool judge(){if(tempx>=0&&tempx=0&&tempyreturn true;else return false;}bool find(int x,int y){if(x==tx&&y==ty)return true;for(register int i=0;i<4;++i){tempx=x+mx[i];tempy=y+my[i];i f(tag[tempx][tempy]==false&&judge()&&matrix[tempx][tempy])tag[tempx][tempy]=1;if(find(tempx,tempy))return true;else tag[tempx][tempy]=false; }}return false;}2、How many setsint n,m;int count;void find(int start,int num){if(num==m){count++;return;}for(register int i=start;i<=n;++i) {find(i+2,num+1);}return;}⼴搜：1、knight movesstruct point{short x;short y;};short mx[]={1,2,2,1,-1,-2,-2,-1}; short my[]={2,1,-1,-2,2,1,-1,-2}; bool judge(int x,int y)if(x>0&&x<9&&y>0&&y<9)return true; else return false;}int bfs(point start,point end){bool tag[9][9]={0};int path[9][9]={0};queueq;q.push(start);tag[start.x][start.y]=1;struct point cur,nex;while(!q.empty()){cur=q.front();q.pop();if(cur.x==end.x&&cur.y==end.y) return path[cur.x][cur.y];for(register int i=0;i<8;++i){nex=cur;nex.x+=mx[i];nex.y+=my[i];if(!tag[nex.x][nex.y]&&judge(nex.x,nex.y)){q.push(nex);tag[nex.x][nex.y]=1;path[nex.x][nex.y]=path[cur.x][cur.y]+1;}}}return path[end.x][end.y];}int jie[9]={0,1,2,6,24,120,720,5040,40320}; struct points {string steps;int num;};int contor(int num){int temp[9],result=0,count;for(register int i=8;i>=1;--i){temp[i]=num%10;num/=10;}for(register int i=1;i<=8;++i){count=0;for(register int j=i+1;j<=8;++j)if(temp[i]>temp[j]) ++count;result+=count*jie[8-i];}return result;}while(!q.empty()){cur=q.front();q.pop();if(cur.steps.size()>limit){cout<<"-1\n";break;}if(cur.num==target){cout<}temp=cur.num;fac[0]=A(temp);fac[1]=B(temp);fac[2]=C(temp);for(register int i=0;i<3;++i){con=contor(fac[i]);if(lable[con]==0){lable[con]=1;next.num=fac[i];next.steps=cur.steps+char('A'+i); q.push(next);}}}3、马的周游问题（剪枝）bool dfs(int x,int y,int count){if(count==64){path[count]=(x-1)*8+y;return true;}vectorv;struct points cur;visit[x][y]=1;for(register int i=0;i<8;++i){if(judge(x+mx[i],y+my[i])){cur.x=x+mx[i];cur.y=y+my[i];v.push_back(cur);}}sort(v.begin(),v.end(),comp);//剪枝short size=v.size();for(register short i=0;i{if(dfs(v[i].x,v[i].y,count+1)){path[count]=(v[i].x-1)*8+v[i].y; return true;}}visit[x][y]=0;return false;}图论：Dijkstra算法：1、Campusvoid dijkstra(int start,int end,int count) {int minalen=0,index;memset(tag,false,sizeof(tag));for(register int i=0;i{mina[i]=road[start][i];}mina[start]=0;tag[start]=1;for(int k=0;k{minalen=INF;for(register int i=0;i{if(mina[i]{minalen=mina[i];index=i;}}tag[index]=1;if(index==end)break;for(register int i=0;i{if(!tag[i])if(mina[i]>(minalen+road[index][i])) mina[i]=minalen+road[index][i];}}}2、kruskal算法for(register int k=0;kfor(register int i=0;ifor(register int j=0;j{if(dist[i][j]!=-1||dist[i][k]+ dist[k][j] dist[i][j]=dist[i][k]+dist[k][j];//Path[i][j]=Path[k][j];}3、prim算法for(register int j=1;j{minlen=MAX;for(register int i=1;i{if(!tag[i]&&dist[i]{index=i;}}tag[index]=1;if(maxfor(register int i=1;i{if(!tag[i]&&dist[i]>road[index][i]) dist[i]=road[index][i];}}图的存储、并查集1、邻接表struct node{int end;int len;node(int e,int l){end=e;len=l;}};vectorM[maxn];for(register int i=1;i{cin>>from>>to>>l;node N1(to,l);node N2(from,l);M[from].push_back(N1);M[to].push_back(N2);}2、并查集int father[MAX];int Rank[MAX];{father[x]=x;Rank[x]=0;}int Find_Set(int x){if(x!=father[x]){father[x]=Find_Set(father[x]);}return father[x];}void Union(int x,int y){x=Find_Set(x);y=Find_Set(y);if(x==y)return;if(Rank[x]>Rank[y]){father[y]=x;}else{if(Rank[x]==Rank[y]){Rank[y]++;}father[x]=y;}}int main(){int x,y;memset(father,-1,sizeof(father)); memset(Rank,0,sizeof(Rank));while(cin>>x>>y){if(father[x]==-1)Make_Set(x);if(father[y]==-1)Make_Set(y);if(Find_Set(x)!=Find_Set(y))cout<Union(x,y);}return0;}动态规划（DP背包）1、采药2、int value[maxnv];3、int max(int a,int b){4、return a>b?a:b;5、}6、for(i=0;i7、for(j=t;j>=w[i];j--)value[j]=max(value[j],value[j-w[i]]+v[i]);8、cout<9、return 0;10、}⾼精度1、⾼精度加法void add(int sum[],int num[]){for(int i=0;i<200;i++){sum[i]=sum[i]+num[i];sum[i+1]+=sum[i]/10;sum[i]=sum[i]%10;}}2、⾼精度乘法void mutiply(int sum[],int num[])int numsize;int store[200];register int i,j,k,carry=0,tempcarry;for(i=199;i>=0;i--)if(num[i]!=0){numsize=i;break;} for(i=0;i<200;i++) store[i]=sum[i];memset(sum,0,200*sizeof(int));for(j=0;j<=numsize;j++){memset(temp,0,200*sizeof(int));for(k=0;k<200-j;k++){temp[k+j]=store[k];}for(i=0;i<200;i++){temp[i]=num[j]*temp[i];tempcarry=temp[i]/10;temp[i]=temp[i]%10+carry;carry=tempcarry;carry+=temp[i]/10;temp[i]=temp[i]%10;}add(sum,temp);}}KMP算法int index_KMP(char*s,char*t,int pos){int i=pos,j=1;while(i<=(int)strlen(s)&&j<=(int)strlen(t)) {if(j==0||s[i]==t[j-1]){j++;}else j=next[j];}if(j>(int)strlen(t))return i-strlen(t)+1;elsereturn0;}void get_next(char*t,int*next) {int i=1,j=0;next[0]=next[1]=0;while(i<(int)strlen(t)){if(j==0||t[i]==t[j]){i++;j++;next[i]=j;}else j=next[j];}}int main(){int n;get_next(t,next);n=index_KMP(s,t,pos); printf("%d",n);return0;}并查集int father[maxn] = {0};int Rank[maxn] = {0};void make_set(int x){father[x] = x;Rank[x] = 0;}int find_set(int x){if(father[x] != x){father[x] = find_set(father[x]); }return father[x];}void union_set(int x, int y) {x = find_set(x);y = find_set(y);if(x == y) return;if(Rank[x] > Rank[y]){father[y] = x;}else{if(Rank[x] == Rank[y]){Rank[y]++;}father[x] = y;}}。