【最近公共祖先】

〖模板代碼〗

? [倍增算法]

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 } View Code

? [樹鏈剖分]

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 } View Code

〖相關題目〗

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\n",di[a]+di[b]-2*di[solve(a,b)]); 56 } 57 return 0; 58 } View Code

【網絡流】

〖相關知識〗

[無源匯有上下界可行流]

模型：給出一個網絡，每條邊的流量有一個上界 $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 } View Code

? [最小費用最大流]

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 } View Code

〖相關題目〗

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 } View Code

【二分圖匹配】

〖相關資料〗

《二分圖匹配》

〖相關知識〗

點覆蓋：對于圖中所有的邊，至少有一個端點屬于該點集；最小點覆蓋=最大匹配。

邊覆蓋：對于圖中所有的點，該邊集中至少有一條邊以其為頂點；最小邊覆蓋=總點數-最大匹配。

獨立集：該點集中任意兩點之間都不存在邊；最大獨立集=總點數-最小點覆蓋。

有向無環圖最小不相交路徑覆蓋：用最少的不相交路徑覆蓋所有頂點；原圖每個點i拆成i₁與i₂，若原圖中如果存在邊 (x, y)，那么就連接x₁, y₂，原圖的最小路徑覆蓋=原圖總點數 n - 二分圖最大匹配?。

有向無環圖最小可相交路徑覆蓋：用最少的可相交路徑覆蓋所有頂點；將原圖做一次Floyd傳遞閉包，如果兩個點x 可以到達 y，連接x₁, y₂，將問題轉化為最小不相交路徑覆蓋。

鏈：鏈上任意兩個點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 } View Code

〖相關題目〗

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 } View Code

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",n-ans); 51 return 0; 52 } View Code

【最小生成樹】

〖模板代碼〗

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 } View Code

【最短路】

〖模板代碼〗

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 } View Code

【有向圖的強連通分量】

〖模板代碼〗

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 } View Code

【無向圖的點雙連通分量】

〖模板代碼〗

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\n",ans); 50 for(int i=1;i<=n;i++) 51 if(iscut[i])printf("%d ",i); 52 return 0; 53 } View Code

? ?

轉載于:https://www.cnblogs.com/zsnuo/p/8886357.html

總結

以上是生活随笔為你收集整理的【算法总结】图论相关的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。