Tarjian算法LCA
1.LCA(u)
2.{
3.Make-Set(u)
4.ancestor[Find-Set(u)]=u
5.对于u的每一个孩子v
6.{
7.LCA(v)
8.Union(u)
9.ancestor[Find-Set(u)]=u
10.}
11.checked[u]=true
12.对于每个(u,v)属于P
13.{
14.if checked[v]=true
15.then{
16.回答u和v的最近公共祖先为ancestor[Find-Set(v)]
17.}
18.}
19.}
RMQ-ST一维及二维算法
一维
/*Sparse Table(ST)init O(nlogn)query O(1)*/
1.#include
2.#include
3.#include
https://www.doczj.com/doc/0f2602858.html,ing namespace std;
5.const int MAXN=10000;
6.int m[MAXN][14],a[MAXN],n;
7./*
8.m数组的第二维的大小可以根据MAXN算出来填到里面logMAXN
9.*/
10.void process()
11.{
12.//initialize m for the intervals with length1
13.for(int i=0;i 14.{ 15.m[i][0]=i; 16.} 17.for(int j=1;(1< 18.{ 19.for(int i=0;i+(1< 20.{ 21.if(a[m[i][j-1]] 22.{ 23.m[i][j]=m[i][j-1]; 24.} 25.else 26.{ 27.m[i][j]=m[i+(1<<(j-1))][j-1]; 28.} 29.} 30.} 31.return; 32.} 33.int rmq(int i,int j) 34.{ 35.int k=(int)(log(j-i+1)/log(2)); 36.int step=(int)pow(2.0,(double)k); 37.return a[m[j-step+1][k]]>=a[m[i][k]]?m[i][k]:m[j-step+1][k]; 38.} 39.int main() 40.{ 41.//计算m数组的第二维大小 42./* 43.printf("%d\n",(int)(log(MAXN)/log(2))+1); 44.return0; 45.*/ 46./*主函数中输入待询问的数组a，要询问的一系列区间s[i,j]*/ 47.int i,j; 48.while(scanf("%d",&n)==1&&n>0) 49.{ 50.for(i=0;i 51.{ 52.scanf("%d",&a[i]); 53.} 54.process();//预处理 55.while(scanf("%d%d",&i,&j)==2&&i+j>=0) 56.{ 57.printf("%d\n",a[rmq(i,j)]); 58.} 59.} 60.return0; 61.} 二维 1.#include 2.#include 3.#include https://www.doczj.com/doc/0f2602858.html,ing namespace std; 5.#define MAXN302 6.#define MAXM302 7.int dp2[MAXN][MAXM][10][10],bb[302][302]; 8.void makermq(int n,int m,int b[][MAXM]) 9.{ 10.int row,col,i,j; 11.for(row=1;row<=n;row++) 12.for(col=1;col<=m;col++) 13.dp2[row][col][0][0]=b[row][col]; 14.for(i=0;(1< 15.for(j=0;(1< 16.{ 17.if(i==0&&j==0)continue; 18.for(row=1;row+(1< 19.for(col=1;col+(1< 20.{ 21.if(i==0) 22.dp2[row][col][i][j]=max(dp2[row][col][i][j- 1],dp2[row][col+(1<<(j-1))][i][j-1]); 23.else 24.dp2[row][col][i][j]=max(dp2[row][col][i- 1][j],dp2[row+(1<<(i-1))][col][i-1][j]); 25.} 26.} 27.} 28.int rmq(int sx,int ex,int sy,int ey) 29.{ 30.int kx=(int)(log((ex-sx+1)*1.0)/log(2.0)),ky=(int)(log((ey-sy+1)*1.0)/log(2.0)); 31.return max(max(dp2[sx][sy][kx][ky],dp2[sx][ey-(1< (1< 32.} 小根堆 1.int heap[100005]; 2.int heap_size; 3.void heap_keep(int i) 4.{ 5.int child; 6.int temp; 7.temp=heap[i]; 8.while(2*i<=heap_size) 9.{ 10.child=2*i; 11.if(child 12.child+=1; 13.if(temp>heap[child]) 14.{ 15.heap[i]=heap[child]; 16.i=child; 17.} 18.else 19.break; 20.} 21.heap[i]=temp; 22.} 23.void heap_insert(int val) 24.{ 25.int temp; 26.int i; 27.heap_size++; 28.i=heap_size; 29.heap[heap_size]=val; 30.temp=val; 31.while(i>1) 32.{ 33.if(temp 34.{ 35.heap[i]=heap[i/2]; 36.i/=2; 37.} 38.else 39.break; 40.} 41.heap[i]=temp; 42.} 43.int pop() 44.{ 45.int min; 46.min=heap[1]; 47.heap[1]=heap[heap_size]; 48.heap_size--; 49.heap_keep(1); 50.return min; 51.} 无向图的双连通分量 求点双连通分量：求割点+缩点 /* (1)n为顶点数,标号从1开始 (2)c为原图的邻接表 (3)G[1]..G[tot]存储每个V_BCC中的所有点 (4)num[u]表示原图中的点u属于新图中的第num[u]个V_BCC (5)对割点而言,num[u]没有意义 (6)sub[u]表示去掉点u会将原图分裂为sub[u]个连通块 */ 1.#include 2.#include https://www.doczj.com/doc/0f2602858.html,ing namespace std; 4.const int N=1024; 5.const int M=100000; 6.struct List{ 7.int v; 8.List*next; 9.}pool[M],*c[N],*pp; 10.inline void add_edge(int u,int v) 11.{ 12.pp->v=v; 13.pp->next=c[u]; 14.c[u]=pp++; 15.} 16.int n,m,label,tot,top,rid,rsub; 17.int low[N],dfn[N],num[N],sub[N],stack[N]; 18.vector 19.void V_BCC_VISIT(int u) 20.{ 21.low[u]=dfn[u]=label++; 22.stack[++top]=u; 23.for(List*p=c[u];p;p=p->next){ 24.int v=p->v; 25.if(dfn[v]){low[u] 26.V_BCC_VISIT(v); 27.low[u] 28.if(low[v]>=dfn[u]){ 29.if(u==rid)++rsub; 30.else++sub[u]; 31.++tot; 32.do{ 33.num[stack[top]]=tot; 34.G[tot].push_back(stack[top]); 35.}while(stack[top--]!=v); 36.num[u]=tot; 37.G[tot].push_back(u); 38.} 39.} 40.} 41.void V_BCC() 42.{ 43.int i; https://www.doczj.com/doc/0f2602858.html,bel=1; 45.top=-1; 46.tot=0; 47.for(i=1;i<=n;++i)dfn[i]=0,sub[i]=1,G[i].clear(); 48.for(i=1;i<=n;++i) 49.if(dfn[i]==0){ 50.rid=i; 51.rsub=0; 52.V_BCC_VISIT(i); 53.sub[rid]=rsub; 54.} 55.} 56.int main() 57.{ 58.int i,j; 59.while(scanf("%d%d",&n,&m)==2){ 60.for(i=1;i<=n;++i)c[i]=NULL; 61.pp=pool; 62.while(m--){ 63.scanf("%d%d",&i,&j); 64.add_edge(i,j); 65.add_edge(j,i); 66.} 67.V_BCC(); 68.} 69.return0; 70.} 求边双连通分量：求桥+缩点 /* (1)n为顶点数,标号从1开始 (2)c为原图的邻接表,g为E_BCC图的邻接表 (3)num[u]表示原图中的点u属于新图中的第num[u]个E_BCC (4)edge[]存储所有的桥 (5)注意pool[M]要开得足够大以容得下新旧两个图中所有的边 (6)E_BCC图中去掉了自环(显然不存在多重边) */ 1.#include 2.#include 3.const int N=505; 4.const int M=20005; 5.struct List{ 6.int v,id; 7.List*next; 8.}pool[M],*c[N],*g[N],*pp; 9.inline void add_edge(int u,int v,int id,List*c[]) 10.{ 11.pp->v=v; 12.pp->id=id; 13.pp->next=c[u]; 14.c[u]=pp++; 15.} 16.struct Edge{ 17.int u,v; 18.}edge[M]; 19.int n,m,label,tot,top; 20.int low[N],dfn[N],num[N],stack[N]; 21.bool eflag[M]; 22.void E_BCC_VISIT(int u) 23.{ 24.low[u]=dfn[u]=label++; 25.stack[++top]=u; 26.for(List*p=c[u];p;p=p->next){ 27.int v=p->v; 28.if(eflag[p->id])continue; 29.eflag[p->id]=true; 30.if(dfn[v]){low[u] 31.E_BCC_VISIT(v); 32.low[u] 33.if(low[v]>dfn[u]){ 34.edge[m].u=u; 35.edge[m++].v=v; 36.++tot; 37.do{ 38.num[stack[top]]=tot; 39.}while(stack[top--]!=v); 40.} 41.} 42.} 43.void E_BCC() 44.{ 45.int i; 46.tot=0; 47.m=0; 48.for(i=1;i<=n;++i)dfn[i]=0,num[i]=-1; 49.for(i=0;i 50.for(i=1;i<=n;++i) 51.if(dfn[i]==0){ https://www.doczj.com/doc/0f2602858.html,bel=1; 53.top=-1; 54.E_BCC_VISIT(i); 55.++tot; 56.while(top>=0){ 57.num[stack[top]]=tot; 58.--top; 59.} 60.} 61.for(i=1;i<=tot;++i)g[i]=NULL; 62.for(i=1;i<=n;++i){ 63.int u=num[i]; 64.for(List*p=c[i];p;p=p->next){ 65.int v=num[p->v]; 66.if(u!=v)add_edge(u,v,0,g); 67.} 68.} 69.} 70.int main() 71.{ 72.int i,j,k; 73.while(scanf("%d%d",&n,&m)==2){ 74.for(i=1;i<=n;++i)c[i]=NULL; 75.pp=pool; 76.for(k=0;k 77.scanf("%d%d",&i,&j); 78.add_edge(i,j,k,c); 79.add_edge(j,i,k,c); 80.} 81.E_BCC(); 82.} 83.return0; 84.} 有向图的强连通分量 求强连通分量+缩点 /* (1)n为顶点数,标号从1开始 (2)c为原图的邻接表,g为SCC图的邻接表 (3)num[u]表示原图中的点u属于新图中的第num[u]个SCC (4)注意pool[M]要开得足够大以容得下新旧两个图中所有的边 (5)SCC图中去掉了自环和多重边 */ 1.#include 2.#include 3.const int N=5005; 4.const int M=100005; 5.struct List{ 6.int v; 7.List*next; 8.}pool[M],*c[N],*g[N],*pp; 9.inline void add_edge(int u,int v,List*c[]) 10.{ 11.pp->v=v; 12.pp->next=c[u]; 13.c[u]=pp++; 14.} 15.int n,m,label,tot,top; 16.int low[N],dfn[N],num[N],stack[N],hash[N]; 17.bool used[N]; 18.void SCC_VISIT(int u) 19.{ 20.low[u]=dfn[u]=label++; 21.stack[++top]=u; 22.for(List*p=c[u];p;p=p->next){ 23.int v=p->v; 24.if(used[v])continue; 25.if(dfn[v]==0)SCC_VISIT(v),low[u] 26.else low[u] 27.} 28.if(low[u]==dfn[u]){ 29.++tot; 30.do{ 31.num[stack[top]]=tot; https://www.doczj.com/doc/0f2602858.html,ed[stack[top]]=true; 33.}while(stack[top--]!=u); 34.} 35.} 36.void SCC() 37.{ 38.int i; https://www.doczj.com/doc/0f2602858.html,bel=1; 40.top=-1; 41.tot=0; 42.for(i=1;i<=n;++i)dfn[i]=0,used[i]=false; 43.for(i=1;i<=n;++i) 44.if(dfn[i]==0)SCC_VISIT(i); 45.for(i=1;i<=n;++i)hash[i]=-1; 46.for(i=1;i<=tot;++i)g[i]=NULL; 47.for(i=1;i<=n;++i){ 48.int u=num[i]; 49.for(List*p=c[i];p;p=p->next){ 50.int v=num[p->v]; 51.if(u!=v&&hash[v]!=u)hash[v]=u,add_edge(u,v,g); 52.} 53.} 54.} 55.int main() 56.{ 57.int i,j; 58.while(scanf("%d",&n)==1&&n){ 59.for(i=1;i<=n;++i)c[i]=NULL; 60.pp=pool; 61.scanf("%d",&m); 62.while(m--){ 63.scanf("%d%d",&i,&j); 64.add_edge(i,j,c); 65.} 66.SCC(); 67.} 68.return0; 69.} 前K短路 第k短路径问题；用类似A*算法的函数去求第k短路径。先通过dijkstra求出各节点到终点的最短路径，用这个当A*中函数的h(n),g(n)为当前已走路径。 因为这里的h(x)本身就是h*(x)，当然满足h(x)<=h*(x)。因此可以说，在每次出队列的状态x中，第一次遇到x.v==t时，就找到了从s到t的第一短的路径，它的长度就是f(x)……第k次遇到x.v==t时，就找到了从s到t的第k短的路径。 1.#include 2.#include 3.#include 4.#include https://www.doczj.com/doc/0f2602858.html,ing namespace std; 6.#define MAXN1001 7.#define INF0x7f7f7f7f 8.typedef pair 9.//typedef make_pair MP; 10.int dist[MAXN],n,m,S,T,K,cnt[MAXN]; 11.vector 12.struct path 13.{ 14.int v,g; 15.path(){}; 16.path(int a,int b):v(a),g(b){} 17.}; 18.void dijkstra() 19.{ 20.int i,u,len,v,cost; 21.priority_queue 22.//priority_queue 23.memset(dist,0x7f,sizeof(dist)); 24.dist[T]=0; 25.qu.push(make_pair(0,T)); 26.while(!qu.empty()) 27.{ 28.u=qu.top().second; 29.len=qu.top().first; 30.qu.pop(); 31.if(dist[u]!=len)//该路径并不是局部最短路，故不作扩展 32.continue; 33.for(i=0;i 34.{ 35.v=map1[u][i].second; 36.cost=map1[u][i].first; 37.if(dist[v]>dist[u]+cost) 38.{ 39.dist[v]=dist[u]+cost; 40.qu.push(make_pair(dist[v],v)); 41.} 42.} 43.} 44.} 45.class CP 46.{ 47.public: 48.int operator()(path&a,path&b) 49.{ 50.return a.g+dist[a.v]>b.g+dist[b.v];//最小堆 51.} 52.}; 53.int astar() 54.{ 55.int i,v,cost,len; 56.memset(cnt,0,sizeof(cnt)); 57.priority_queue 58.if(S==T)K++; 59.if(dist[S]==INF) 60.return-1; 61.qu.push(path(S,0)); 62.while(!qu.empty()) 63.{ 64.v=qu.top().v; 65.len=qu.top().g; 66.qu.pop(); https://www.doczj.com/doc/0f2602858.html,t[v]++; 68.if(cnt[T]==K) 69.return len; 70.if(cnt[v]>K)//若v是S到T的K短路上的一点，则cnt[v]不可能大于K，否则 已至少有从S到T的cnr[v]-1条比现计划路径短的路径，与v是S到T的K短路上的一点矛盾 71.continue; 72.for(i=0;i 73.qu.push(path(map2[v][i].second,len+map2[v][i].first)); 74.} 75.return-1; 76.} 77.int main() 78.{ 79.int i,x,y,d; 80.scanf("%d%d",&n,&m); 81.for(i=0;i 82.{ 83.scanf("%d%d%d",&x,&y,&d); 84.map1[y].push_back(make_pair(d,x)); 85.map2[x].push_back(make_pair(d,y)); 86.} 87.scanf("%d%d%d",&S,&T,&K); 88.dijkstra(); 89.printf("%d\n",astar()); 90.return0; 91.} 生成树计数 /*This Code is Submitted by Debug cool for Problem2535at2009-09-0811:25:39*/ 1.#include 2.#include 3.#define zero(x)((x>0?x:-x)<1e-15) https://www.doczj.com/doc/0f2602858.html,ing namespace std; 5.int const MAXN=100; 6.double a[MAXN][MAXN]; 7.double b[MAXN][MAXN]; 8.int g[MAXN][MAXN]; 9.int N; 10.double det(double a[MAXN][MAXN],int n) 11.{ 12.int i,j,k,sign=0; 13.double ret=1,t; 14.for(i=0;i 15.for(j=0;j 16.b[i][j]=a[i][j]; 17.for(i=0;i 18.{ 19.if(zero(b[i][i])) 20.{ 21.for(j=i+1;j 22.if(!zero(b[j][i])) 23.break; 24.if(j==n) 25.return0; 26.for(k=i;k 27.t=b[i][k],b[i][k]=b[j][k],b[j][k]=t; 28.sign++; 29.} 30.ret*=b[i][i]; 31.for(k=i+1;k 32.b[i][k]/=b[i][i]; 33.for(j=i+1;j 34.for(k=i+1;k 35.b[j][k]-=b[j][i]*b[i][k]; 36.} 37.if(sign&1) 38.ret=-ret; 39.return ret; 40.} 41.int main() 42.{ 43.int cas; 44.scanf("%d",&cas); 45.while(cas--) 46.{ 47.scanf("%d",&N); 48.for(int i=0;i 49.for(int j=0;j 50.{ 51.scanf("%d",&g[i][j]); 52.a[i][j]=0; 53.} 54.for(int i=0;i 55.{ 56.g[i][i]=0; 57.int d=0; 58.for(int j=0;j 59.if(g[i][j]) 60.d++; 61.a[i][i]=d; 62.} 63.for(int i=0;i 64.for(int j=0;j 65.if(g[i][j]) 66.a[i][j]=-1; 67.double ans=det(a,N-1); 68.printf("%0.0lf\n",ans); 69.} 70.return0; 71.} 次小生成树 1.#include 2.#include 3.#include 4.#include https://www.doczj.com/doc/0f2602858.html,ing namespace std; 6.const int N=105; 7.class edge{ 8.public: 9.int u,v,dis; 10.edge(){} 11.edge(int_u,int_v,int_dis):u(_u),v(_v),dis(_dis){} 12.bool operator<(const edge&T)const{ 13.return dis>T.dis; 14.} 15.}; 16.int cas,n,m,dis[N],ans[N],f[N][N],dp[N][N]; 17.bool tree_edge[N][N],mark[N]; 18.vector 19.priority_queue 20.int first_prim() 21.{ 22.int res=0,cnt=0; 23.memset(tree_edge,false,sizeof(tree_edge)); 24.memset(mark,false,sizeof(mark)); 25.memset(dp,-1,sizeof(dp)); 26.while(!Q.empty())Q.pop(); 27.Q.push(edge(0,1,0)); 28.while(!Q.empty()){ 29.edge top=Q.top(); 30.int u=top.u,v=top.v,d=top.dis; 31.Q.pop(); 32.if(mark[v]==true)continue; 33.ans[cnt]=v; 34.mark[v]=true; 35.if(u!=0)tree_edge[u][v]=tree_edge[v][u]=true; 36.for(int j=0;j<=cnt-1;j++) 37.dp[v][ans[j]]=dp[ans[j]][v]=max(f[u][v],dp[ans[j]][u]); 38.for(size_t i=0;i 39.if(!mark[g[v][i].v])Q.push(g[v][i]); https://www.doczj.com/doc/0f2602858.html,t++; 41.res+=d; 42.} 43.return res; 44.} 45.int second_prim(int least) 46.{ 47.int res=(1<<28); 48.for(int i=1;i<=n;i++) 49.{ 50.for(int j=i+1;j<=n;j++){ 51.if(f[i][j]==-1||tree_edge[i][j])continue; 52.res=min(res,least+f[i][j]-dp[i][j]); 53.} 54.} 55.return res; 56.} 57.int main() 58.{ 59.for(scanf("%d",&cas);cas;cas--){ 60.memset(f,-1,sizeof(f)); 61.for(int i=0;i 62.scanf("%d%d",&n,&m); 63.for(int i=0;i 64.int u,v,d; 65.scanf("%d%d%d",&u,&v,&d); 66.f[u][v]=f[v][u]=d; 67.g[u].push_back(edge(u,v,d)); 68.g[v].push_back(edge(v,u,d)); 69.} 70.int first_cost=first_prim(); 71.int second_cost=second_prim(first_cost); 72.if(first_cost!=second_cost) 73.printf("%d\n",first_cost); 74.else 75.printf("Not Unique!\n"); 76.} 77.return0; 78.} 最小度限制生成树 /*This Code is Submitted by Debug cool for Problem1658at2009-09-0712:24:00*/ 1.#include 2.#include 3.#include 4.#define MAXN25 5.#define INF10000000 https://www.doczj.com/doc/0f2602858.html,ing namespace std; 7.map 8.int Knum,cnt,cost[MAXN][MAXN],point[MAXN]; 9.bool vis[MAXN],Tedge[MAXN][MAXN]; 10.void init() 11.{ 12.mymap.clear(); 13.for(int i=0;i 14.for(int j=0;j 15.cost[i][j]=INF; 16.} 17.int prim() 18.{ 19.int ans=0,ver,mn,lowcost[MAXN],pre[MAXN]; 20.bool flag[MAXN]; 21.for(int i=2;i<=cnt;i++) 22.{ 23.pre[i]=2; 24.lowcost[i]=cost[2][i]; 25.flag[i]=false; 26.} 27.flag[2]=true; 28.int left=cnt-2; 29.while(left--) 30.{ 31.mn=INF+1; 32.for(int i=2;i<=cnt;i++) 33.if(!flag[i]&&lowcost[i] 34.{ 35.mn=lowcost[i]; 36.ver=i; 37.} 38.ans+=mn; 39.flag[ver]=true; 40.Tedge[ver][pre[ver]]=Tedge[pre[ver]][ver]=true; 41.for(int i=2;i<=cnt;i++) 42.if(!flag[i]&&lowcost[i]>cost[ver][i]) 43.{ 44.pre[i]=ver; 45.lowcost[i]=cost[ver][i]; 46.} 47.} 48.return ans; 49.} 50.void DFS(int ver,int count,int&vera,int&verb) 51.{ 52.if(vis[ver]) 53.return; 54.if(ver==1) 55.{ 56.int res=0; 57.for(int i=1;i 58.if(cost[point[i]][point[i-1]]>res) 59.{ 60.res=cost[point[i]][point[i-1]]; 61.vera=point[i]; 62.verb=point[i-1]; 63.} 64.return; 65.} 66.for(int i=1;i<=cnt;i++) 67.{ 68.if(Tedge[ver][i]) 69.{ 70.vis[ver]=true; 71.point[count]=ver; 72.DFS(i,count+1,vera,verb); 73.vis[ver]=false; 74.} 75.} 76.} 77.int work() 78.{ 79.int ver,minimum,mn; 80.memset(Tedge,false,sizeof(Tedge)); 81.minimum=prim(); 82.mn=INF; 83.for(int i=2;i<=cnt;i++) 84.if(mn>cost[i][1]) 85.{ 86.mn=cost[i][1]; 87.ver=i; 88.} 89.minimum+=mn; 90.Tedge[ver][1]=Tedge[1][ver]=true; 91.for(int i=2;i<=Knum&&i 92.{ 93.int dmost=INF; 94.int pa=0,pb=0,vera=0,verb=0; 95.for(int j=2;j<=cnt;j++) 96.{ 97.if(!Tedge[j][1]&&cost[j][1] 98.{ 99.memset(vis,false,sizeof(vis)); 100.memset(point,0,sizeof(point)); 101.DFS(j,0,vera,verb); 102.if(cost[1][j]-cost[vera][verb] 104.dmost=cost[1][j]-cost[vera][verb]; 105.pa=vera; 106.pb=verb; 107.ver=j; 108.} 109.} 110.} 111.if(dmost<0) 112.minimum+=dmost; 113.else 114.break; 115.Tedge[1][ver]=Tedge[ver][1]=1;
相关主题
文本预览