【最近公共祖先】
〖模板代码〗
[倍增算法]
1 void dfs(int k) 2 { 3 for(int i=1;(1<<i)<=deep[k];i++) 4 x[k][i]=x[x[k][i-1]][i-1]; 5 for(int i=head[k];i;i=e[i].next) 6 { 7 if(deep[e[i].to])continue; 8 x[e[i].to][0]=k; 9 deep[e[i].to]=deep[k]+1; 10 di[e[i].to]=di[k]+e[i].w; 11 dfs(e[i].to); 12 } 13 } 14 int lca(int ri,int rj) 15 { 16 if(deep[ri]<deep[rj])swap(ri,rj); 17 int d=deep[ri]-deep[rj]; 18 for(int i=0;(1<<i)<=d;i++) 19 if((1<<i)&d)ri=x[ri][i]; 20 if(ri==rj)return ri; 21 for(int i=16;i>=0;i--) 22 if((1<<i)<=deep[rj]&&x[ri][i]!=x[rj][i]) 23 ri=x[ri][i],rj=x[rj][i]; 24 return x[ri][0]; 25 }
[树链剖分]
1 void dfs1(int x) 2 { 3 sz[x]=1; 4 for(int i=first[x];i;i=e[i].next) 5 { 6 int to=e[i].to; 7 deep[to]=deep[x]+1; 8 fa[to]=x; 9 dfs1(to);sz[x]+=sz[to]; 10 if(sz[to]>sz[son[x]])son[x]=to; 11 } 12 } 13 void dfs2(int x) 14 { 15 if(x==son[fa[x]])top[x]=top[fa[x]]; 16 else top[x]=x; 17 for(int i=first[x];i;i=e[i].next)dfs2(e[i].to); 18 } 19 int lca(int x,int y) 20 { 21 for(;top[x]!=top[y];deep[top[x]]>deep[top[y]]?x=fa[top[x]]:y=fa[top[y]]); 22 return deep[x]<deep[y]?x:y; 23 }
〖相关题目〗
1.【codevs2370】小机房的树
题意:见原题
分析:见代码
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=50010; 5 struct point{int from,to,v;}e[maxn*2]; 6 int n,m,cnt,a,b,c; 7 int head[maxn],deep[maxn],x[maxn][17],di[maxn]; 8 //deep数组表示节点所在的层数,di数组表示节点到根节点的距离 9 //x[i][j]的含义为:节点i的祖先中与其相差2^j层的节点;例如,x[i][0]代表节点i的父亲 10 bool f[maxn];//判断节点是否访问过 11 void add(int a,int b,int c)//邻接表建边 12 {cnt++;e[cnt].from=head[a];e[cnt].to=b;e[cnt].v=c;head[a]=cnt;} 13 void dfs(int k) 14 { 15 f[k]=true; 16 for(int i=1;(1<<i)<=deep[k];i++) 17 x[k][i]=x[x[k][i-1]][i-1];//递推得出x数组 18 for(int i=head[k];i;i=e[i].from) 19 { 20 if(!f[e[i].to]) 21 { 22 x[e[i].to][0]=k;//将节点k标记为e[i].to的父亲 23 deep[e[i].to]=deep[k]+1;//层数+1 24 di[e[i].to]=di[k]+e[i].v; 25 dfs(e[i].to); 26 } 27 } 28 } 29 int solve(int ri,int rj) 30 { 31 if(deep[ri]<deep[rj])swap(ri,rj); 32 int d=deep[ri]-deep[rj]; 33 for(int i=0;(1<<i)<=d;i++)//利用倍增思想,将ri节点跳到与rj节点同层 34 if((1<<i)&d)ri=x[ri][i]; 35 if(ri==rj)return ri;//找到最近公共祖先 36 for(int i=16;i>=0;i--) 37 if((1<<i)<=deep[rj]&&x[ri][i]!=x[rj][i]) 38 ri=x[ri][i],rj=x[rj][i];//同时往上跳,直到ri与rj为兄弟节点为止 39 return x[ri][0];//返回他们的父亲 40 } 41 int main() 42 { 43 scanf("%d",&n); 44 for(int i=1;i<n;i++) 45 { 46 scanf("%d%d%d",&a,&b,&c); 47 add(a,b,c); 48 add(b,a,c); 49 } 50 dfs(0);//此处假设以0为根节点 51 scanf("%d",&m); 52 while(m--) 53 { 54 scanf("%d%d",&a,&b); 55 printf("%d ",di[a]+di[b]-2*di[solve(a,b)]); 56 } 57 return 0; 58 }
【网络流】
〖相关知识〗
[无源汇有上下界可行流]
模型:给出一个网络,每条边的流量有一个上界 $H_i$ 和一个下界 $L_i$ ,每个点必须满足流量守恒。
分析:首先令每条边的流量等于 $L_i$ ,得到一个不一定满足流量守恒的初始流。令 $a_i$ 表示初始流中点 $i$ 的流入量-流出量。新建附加节点 $SS$ 和 $TT$ ,若 $a_i<0$ ,则新建一条从 $i$ 到 $TT$ 的容量为 $-a_i$ 的边;若 $a_i>0$ ,则新建一条从 $SS$ 到 $i$ 的容量为 $a_i$ 的边。直接跑最大流,若从 $SS$ 出发的所有边都是满流,则存在可行解。原图中每条边的流量为流量下界与附加流之和。
[有源汇有上下界可行流]
分析:从 $T$ 向 $S$ 连一条下界为 $0$ 上界为 $inf$ 的边,即可转化为无源汇有上下界可行流。
[有源汇有上下界最大流]
分析:在残量网络上跑 $S$ 到 $T$ 的最大流。
[有源汇有上下界最小流]
分析:在残量网络上跑 $T$ 到 $S$ 的最大流。
〖模板代码〗
[最小割]
1 int cnt=1; 2 void insert(int u,int v,int w) 3 { 4 e[++cnt]=(edge){v,first[u],w};first[u]=cnt; 5 e[++cnt]=(edge){u,first[v],0};first[v]=cnt; 6 } 7 bool bfs() 8 { 9 memset(dis,-1,sizeof(dis)); 10 int head=0,tail=1; 11 q[head]=S;dis[S]=0; 12 while(head!=tail) 13 { 14 int u=q[head++]; 15 for(int i=first[u];i;i=e[i].next) 16 { 17 int v=e[i].to; 18 if(dis[v]!=-1||!e[i].flow)continue; 19 dis[v]=dis[u]+1; 20 q[tail++]=v; 21 } 22 } 23 return dis[T]!=-1; 24 } 25 int dfs(int u,int a) 26 { 27 if(u==T||a==0)return a; 28 int f,flow=0; 29 for(int& i=cur[u];i;i=e[i].next) 30 { 31 int v=e[i].to; 32 if(dis[v]==dis[u]+1&&(f=dfs(v,min(e[i].flow,a)))>0) 33 { 34 e[i].flow-=f;e[i^1].flow+=f; 35 flow+=f;a-=f;if(a==0)break; 36 } 37 } 38 return flow; 39 } 40 int main() 41 { 42 while(bfs()) 43 { 44 for(int i=S;i<=T;i++)cur[i]=first[i]; 45 ans+=dfs(S,inf); 46 } 47 return 0; 48 }
[最小费用最大流]
1 bool spfa() 2 { 3 memset(inq,0,sizeof(inq));memset(dis,0x3f,sizeof(dis)); 4 int head=0,tail=1;q[0]=T;inq[T]=true;dis[T]=0; 5 while(head!=tail) 6 { 7 u=q[head++];inq[u]=false;if(head>5000)head=0; 8 for(int i=first[u];i;i=e[i].next) 9 { 10 v=e[i].to; 11 if(e[i^1].flow>0&&dis[u]+e[i^1].cost<dis[v]) 12 { 13 dis[v]=dis[u]+e[i^1].cost; 14 if(!inq[v]) 15 { 16 if(dis[v]<dis[q[head]]){head--;if(head<0)head=5000;q[head]=v;} 17 else{q[tail++]=v;if(tail>5000)tail=0;} 18 inq[v]=true; 19 } 20 } 21 } 22 } 23 return dis[S]<inf; 24 } 25 int dfs(int u,int a) 26 { 27 if(u==T||a==0)return a; 28 inq[u]=true;int f,flow=0; 29 for(int& i=cur[u];i;i=e[i].next) 30 { 31 v=e[i].to; 32 if(!inq[v]&&dis[u]==e[i].cost+dis[v]&&(f=dfs(v,min(e[i].flow,a)))>0) 33 { 34 e[i].flow-=f;e[i^1].flow+=f; 35 ans+=e[i].cost*f;flow+=f;a-=f;if(a==0)break; 36 } 37 } 38 return flow; 39 }
〖相关题目〗
1.【codevs1993】草地排水
题意:见原题
分析:见代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 int n,m,a,b,c,ans=0,ansn; 7 int map[210][210],dis[210];//邻接矩阵储存图,dis数组储存分层后节点深度 8 bool bfs()//广搜建立层次图 9 { 10 queue<int>q; 11 memset(dis,-1,sizeof(dis)); 12 q.push(1); 13 dis[1]=0; 14 while(!q.empty()) 15 { 16 int u=q.front(); 17 q.pop(); 18 for(int i=1;i<=n;i++) 19 if(map[u][i]>0&&dis[i]<0)//从顶点u到顶点i的边容量不为0且节点i未被访问过 20 q.push(i),dis[i]=dis[u]+1;//层数+1,并将顶点i丢进广搜队列 21 } 22 if(dis[n]<0)return false;//如果汇点不在层次图上,则算法结束 23 return true; 24 } 25 int find(int k,int low)//在层次图上进行增广 26 { 27 int s; 28 if(k==n||low==0)return low; 29 for(int i=1;i<=n;i++) 30 if(map[k][i]&&dis[i]==dis[k]+1&&(s=find(i,min(low,map[k][i])))) 31 {map[k][i]-=s;map[i][k]+=s;return s;} 32 return 0; 33 } 34 int main() 35 { 36 scanf("%d%d",&m,&n); 37 for(int i=1;i<=m;i++) 38 { 39 scanf("%d%d%d",&a,&b,&c); 40 map[a][b]+=c; 41 } 42 while(bfs()) 43 ans+=find(1,99999999); 44 printf("%d",ans); 45 return 0; 46 }
【二分图匹配】
〖相关资料〗
〖相关知识〗
点覆盖:对于图中所有的边,至少有一个端点属于该点集;最小点覆盖=最大匹配。
边覆盖:对于图中所有的点,该边集中至少有一条边以其为顶点;最小边覆盖=总点数-最大匹配。
独立集:该点集中任意两点之间都不存在边;最大独立集=总点数-最小点覆盖。
有向无环图最小不相交路径覆盖:用最少的不相交路径覆盖所有顶点;原图每个点i拆成i1与i2,若原图中如果存在边 (x, y),那么就连接x1, y2,原图的最小路径覆盖=原图总点数 n - 二分图最大匹配 。
有向无环图最小可相交路径覆盖:用最少的可相交路径覆盖所有顶点;将原图做一次Floyd传递闭包,如果两个点x 可以到达 y,连接x1, y2,将问题转化为最小不相交路径覆盖。
链:链上任意两个点x, y,满足x 能到达y或y能到达x。
反链:链上任意两个点x, y互不可达;最长反链长度=最小链覆盖=有向无环图最小可相交路径覆盖;最长链长度 = 最小反链覆盖。
〖模板代码〗
1 int push(int x) 2 { 3 for(int i=1;i<=m;i++) 4 if(!f[i]&&map[x][i]) 5 { 6 f[i]=true; 7 if(link[i]==-1||push(link[i])) 8 { 9 link[i]=x; 10 return 1; 11 } 12 } 13 return 0; 14 }
〖相关题目〗
1.【codevs2776】寻找代表元
题意:见原题
分析:无
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,m,link[210],to,ans; 6 bool map[210][210],f[210];//邻接矩阵储存 7 int push(int x) 8 { 9 for(int i=1;i<=m;i++) 10 { 11 if(!f[i]&&map[x][i]) 12 { 13 f[i]=true; 14 if(link[i]==-1||push(link[i])) 15 { 16 link[i]=x; 17 return 1; 18 } 19 } 20 } 21 return 0; 22 } 23 int main() 24 { 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;i++) 27 while(1) 28 { 29 scanf("%d",&to); 30 if(!to)break; 31 map[i][to]=true; 32 } 33 memset(link,-1,sizeof(link)); 34 for(int i=1;i<=n;i++) 35 { 36 memset(f,0,sizeof(f)); 37 ans+=push(i); 38 } 39 printf("%d",ans); 40 return 0; 41 }
2.【bzoj1143】[CTSC2008]祭祀river
题意:给定一个有向无环图,求出最大的点集,使得点集中的点两两不可达。
分析:JoeFanの博客
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define ll long long 5 using namespace std; 6 int n,m,u,v,ans,link[205]; 7 bool map[205][205],f[205]; 8 int read() 9 { 10 int x=0,f=1;char c=getchar(); 11 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 12 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 13 return x*f; 14 } 15 int push(int x) 16 { 17 for(int i=n+1;i<=2*n;i++) 18 { 19 if(!f[i]&&map[x][i]) 20 { 21 f[i]=true; 22 if(link[i]==-1||push(link[i])) 23 {link[i]=x; return 1;} 24 } 25 } 26 return 0; 27 } 28 int main() 29 { 30 n=read();m=read(); 31 for(int i=1;i<=m;i++) 32 { 33 u=read();v=read(); 34 map[u][v]=true; 35 } 36 for(int k=1;k<=n;k++) 37 for(int i=1;i<=n;i++) 38 for(int j=1;j<=n;j++) 39 if(map[i][k]&&map[k][j])map[i][j]=true; 40 for(int i=1;i<=n;i++)map[i][i]=false; 41 for(int i=1;i<=n;i++) 42 for(int j=1;j<=n;j++) 43 if(map[i][j])map[i][j+n]=true,map[i][j]=false; 44 memset(link,-1,sizeof(link)); 45 for(int i=1;i<=n;i++) 46 { 47 memset(f,0,sizeof(f)); 48 ans+=push(i); 49 } 50 printf("%d ",n-ans); 51 return 0; 52 }
【最小生成树】
〖模板代码〗
1 int find(int t){return f[t]==t?t:f[t]=find(f[t]);} 2 int main() 3 { 4 n=read();m=read(); 5 for(int i=1;i<=n;i++)f[i]=i; 6 for(int i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),e[i].w=read(); 7 sort(e+1,e+m+1,cmp); 8 for(int i=1;i<=m;i++) 9 { 10 x=find(e[i].x);y=find(e[i].y); 11 if(x==y)continue; 12 f[x]=y;ans+=e[i].w;num++; 13 if(num==n-1)break; 14 } 15 if(num==n-1)printf("%d",ans); 16 else printf("-1"); 17 return 0; 18 }
【最短路】
〖模板代码〗
1 struct node{int id;LL d;bool operator <(const node& a)const{return d>a.d;}}; 2 priority_queue<node>q; 3 void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;} 4 int main() 5 { 6 for(int i=1;i<=n;i++)dis[i]=inf; 7 dis[S]=0;q.push((node){S,0}); 8 while(!q.empty()) 9 { 10 node t=q.top();q.pop();u=t.id; 11 if(dis[t.id]!=t.d)continue; 12 for(int i=first[u];i;i=e[i].next) 13 if(dis[e[i].to]>dis[u]+e[i].w) 14 dis[e[i].to]=dis[u]+e[i].w,q.push((node){e[i].to,dis[e[i].to]}); 15 } 16 }
【有向图的强连通分量】
〖模板代码〗
1 void tarjan(int x) 2 { 3 low[x]=dfn[x]=++tim; 4 sta[++top]=x;vis[x]=true; 5 for(int i=first[x];i;i=e[i].next) 6 { 7 int to=e[i].to; 8 if(!dfn[to])tarjan(to),low[x]=min(low[x],low[to]=min(low[x],low[to])); 9 else if(vis[to])low[x]=min(low[x],dfn[to]); 10 } 11 if(low[x]==dfn[x]) 12 { 13 color++; 14 while(sta[top]!=x)vis[sta[top]]=false,c[sta[top--]]=color; 15 vis[x]=false;c[x]=color;top--; 16 } 17 } 18 int main() 19 { 20 for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); 21 return 0; 22 }
【无向图的点双连通分量】
〖模板代码〗
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define LL long long 5 using namespace std; 6 const int N=1e5+5; 7 int n,m,x,y,cnt=1,tim,ans; 8 int first[N],dfn[N],low[N]; 9 bool iscut[N]; 10 struct edge{int to,next;}e[N*2]; 11 int read() 12 { 13 int x=0,f=1;char c=getchar(); 14 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 15 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 16 return x*f; 17 } 18 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;} 19 void tarjan(int x,int fa) 20 { 21 dfn[x]=low[x]=++tim; 22 int son=0; 23 for(int i=first[x];i;i=e[i].next) 24 { 25 int to=e[i].to; 26 if(to==fa)continue; 27 if(!dfn[to]) 28 { 29 son++;tarjan(to,x); 30 low[x]=min(low[x],low[to]); 31 if(low[to]>=dfn[x])iscut[x]=true; 32 } 33 else low[x]=min(low[x],dfn[to]); 34 } 35 if(fa<0&&son<=1)iscut[x]=false; 36 } 37 int main() 38 { 39 n=read();m=read(); 40 for(int i=1;i<=m;i++) 41 { 42 x=read();y=read(); 43 ins(x,y);ins(y,x); 44 } 45 for(int i=1;i<=n;i++) 46 if(!dfn[i])tarjan(i,-1); 47 for(int i=1;i<=n;i++) 48 if(iscut[i])ans++; 49 printf("%d ",ans); 50 for(int i=1;i<=n;i++) 51 if(iscut[i])printf("%d ",i); 52 return 0; 53 }