文章目錄

• • 前言
• 圖論模板
• • 最短路-Floyd
  • 最短路-SPFA
  • 最短路-Dij+堆優(yōu)化
  • 最小生成樹-Kruskal
  • 最小生成樹-Prim+堆優(yōu)化
  • 最大匹配-匈牙利算法
  • tarjan求割點(diǎn)
  • tarjan縮點(diǎn)
  • LCA-樹上倍增
  • LCA-tarjan+并查集優(yōu)化
  • 網(wǎng)絡(luò)流-最大流dinic
  • 網(wǎng)絡(luò)流-最小費(fèi)用最大流
  • 負(fù)環(huán)
  • 虛樹
  • 2-SAT
  • Kruskal重構(gòu)樹
  • 靜態(tài)仙人掌

前言

因?yàn)槔鲜菓械么蚰０宓臅r候老是扣不到自己的標(biāo)(因?yàn)橹暗亩即虻锰罅?，所以導(dǎo)致我十分的不爽。便打算開一個模板庫。會不斷更新的

---

圖論模板

最短路-Floyd

for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j];

最短路-SPFA

struct edge_node{int to,next,w; }a[M]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void spfa(int s) {memset(f,0x3f,sizeof(f));q.push(s);v[s]=1;f[s]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y]){v[y]=1;q.push(y);}}}v[x]=false;} }

最短路-Dij+堆優(yōu)化

#include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=100010,M=200010; struct node{int pos,dis;bool operator<(const node &x)const{return x.dis<dis;} }; struct edge_node{int to,next,w; }a[M]; priority_queue<node> q; int tot,ls[N],dis[N],n,m,S; bool v[N]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w; } void dij(int s) {dis[s]=0;q.push((node){s,0});while(!q.empty()){node tmp=q.top();q.pop();int x=tmp.pos;if(v[x]) continue;v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dis[y]>dis[x]+a[i].w){dis[y]=dis[x]+a[i].w;if(!v[y])q.push(node{y,dis[y]});}}} } int main() {scanf("%d%d%d",&n,&m,&S);memset(dis,0x3f,sizeof(dis));for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);}dij(S);for(int i=1;i<=n;i++)printf("%d ",dis[i]); } }

最小生成樹-Kruskal

#include<cstdio> #include<algorithm> using namespace std; const int N=301,M=100010; struct node{int x,y,w; }a[M]; int n,m,fa[N],ans,k; bool cmp(node x,node y) {return x.w<y.w;} int find(int x) {return fa[x]==x?x:find(fa[x]);} int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);for(int i=1;i<=n;i++)fa[i]=i;sort(a+1,a+1+m,cmp);for(int i=1;i<=m;i++){int Fa=find(a[i].x),Fb=find(a[i].y);if(Fa!=Fb){fa[Fb]=Fa;ans+=a[i].w;k++;}if(k==n-1) break;}printf("%d %d",k,ans); }

最小生成樹-Prim+堆優(yōu)化

這個坑先放著，以后再填

最大匹配-匈牙利算法

#include<cstdio> #include<cstring> using namespace std; const int N=1010; struct line{int to,next; }a[N*N]; int link[N],n,m,ls[N],tot,s,e; bool cover[N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } bool find(int x) {int p=0;for (int i=ls[x];i;i=a[i].next){int y=a[i].to;if (!cover[y]){p=link[y];link[y]=x;cover[y]=true;if (!p || find(p)) return true;link[y]=p;}}return false; } int main() {scanf("%d%d%d",&n,&m,&e);for (int i=1;i<=e;i++){int x,y;scanf("%d%d",&x,&y);if(x>m||y>m) continue;addl(x,y);}for (int i=1;i<=n;i++){memset(cover,false,sizeof(cover));if (find(i)) s++;}printf("%d",s); }

tarjan求割點(diǎn)

#include<cstdio> #include<algorithm> #define N 20100 #define M 100100 using namespace std; struct node{int to,next; }a[M*2]; int n,m,tot,dfn[N],low[N],ls[N],cnt,z,root; bool mark[N],v[N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void tarjan(int x) {dfn[x]=low[x]=++cnt;int flag=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;v[y]=0;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);if(dfn[x]<=low[y]){flag++;if((x!=root||flag>1)&&!mark[x])mark[x]=1,z++;}}else low[x]=min(low[x],dfn[y]);} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);if(x==y) continue;addl(x,y);addl(y,x);}for(int i=1;i<=n;i++)if(!dfn[i]) root=i,tarjan(i);printf("%d\n",z);for(int i=1;i<=n;i++)if(mark[i]) printf("%d ",i); }

tarjan縮點(diǎn)

#include<cstdio> #include<stack> #include<queue> #include<cstring> #define N 10000 #define M 100000 using namespace std; stack<int> Stack; queue<int> q; struct line{int to,from,next; }a[M]; int n,m,x,y,tot,in[N],ls[N],fl[N],cost[N],f[N],maxs,low[N],dfn[N],top,num,gt[N],an[N]; bool ins[N],v[N]; void addl(int x,int y,int tot) {a[tot].to=y;a[tot].from=x;a[tot].next=ls[x];ls[x]=tot; } void tarjan(int x) {ins[x]=true;dfn[x]=low[x]=++top;Stack.push(x);for (int i=ls[x];i;i=a[i].next)if (!dfn[a[i].to]){tarjan(a[i].to);low[x]=min(low[x],low[a[i].to]);}else if (ins[a[i].to])low[x]=min(low[x],dfn[a[i].to]);if (low[x]==dfn[x]){while (Stack.top()!=x){int y=Stack.top();fl[y]=x;an[x]+=cost[y];//計算強(qiáng)聯(lián)通權(quán)值和Stack.pop();ins[y]=0;}fl[x]=x;an[x]+=cost[x];//計算強(qiáng)聯(lián)通權(quán)值和ins[x]=0;Stack.pop();} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&cost[i]);for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);addl(x,y,i);//加邊}for (int i=1;i<=n;i++)if (!dfn[i])tarjan(i);//求強(qiáng)聯(lián)通memset(ls,0,sizeof(ls));//去除所有的邊的連通（保留值的）for (int i=1;i<=m;i++){x=a[i].from;y=a[i].to;if (fl[x]!=fl[y])//不在強(qiáng)聯(lián)通中{tot++;addl(fl[x],fl[y],tot);//連邊in[fl[y]]++;//統(tǒng)計入度}} }

LCA-樹上倍增

#include<cstdio> #include<algorithm> #include<queue> #include<cmath> #define N 600001 using namespace std; struct line{int to,next,w; }a[N*5]; int tot,n,m,s,x,y,ls[N],dep[N],f[N][30],dis[N][30],t; queue<int> q; inline int readn() {int X=0,w=0; char c=0;while(c<'0'||c>'9') {w|=c=='-';c=getchar();}while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();return w?-X:X; } inline void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } inline void bfs(int s) {q.push(s);dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for (int i=ls[x];i;i=a[i].next){int y=a[i].to;if (dep[y]) continue;q.push(y);f[y][0]=x;dep[y]=dep[x]+1;dis[y][0]=a[i].w;}}t=(int)(log(n)/log(2))+1;for (int j=1;j<=t;j++){for (int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];dis[i][j]=min(dis[i][j-1],dis[f[i][j-1]][j-1]);}} } inline int LCA(int x,int y) {if (dep[x]>dep[y]) swap(x,y);for (int i=t;i>=0;i--)if (dep[f[y][i]]>=dep[x]) y=f[y][i];if (x==y) return x;for (int i=t;i>=0;i--)if (f[y][i]!=f[x][i]) {x=f[x][i];y=f[y][i];}return f[x][0]; } int main() {n=readn();m=readn();s=readn();for(int i=1;i<n;i++){addl(x=readn(),y=readn(),1);addl(y,x,1);}bfs(s);for(int i=1;i<=m;i++){printf("%d\n",LCA(readn(),readn()));} }

LCA-tarjan+并查集優(yōu)化

#include<cstdio> #include<iostream> using namespace std; struct line{int next,to; }a[20001]; int father[10001],n,m,q,p,v[10001],ans,tot,ls[10001],t,x,y,in[10001]; bool ok; void addl(int x,int y)//加邊 {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } int find(int x)//并查集優(yōu)化 {return x==father[x]?x:find(father[x]); } void tarjan(int x) {v[x]=1;for (int i=ls[x];i;i=a[i].next)//子節(jié)點(diǎn){int y=a[i].to;if (v[y]) continue;tarjan(y);//tarjan一遍father[y]=x;//記錄祖先}if (ok) return;//標(biāo)記已找到if (v[q]==2 && x==p){printf("%d\n",find(q));//輸出ok=true;return;}if (v[p]==2 && x==q)///輸出{printf("%d\n",find(p));ok=true;return;}v[x]=2; } int main() {scanf("%d",&t);for (;t;t--){scanf("%d",&n);tot=0;ok=0;for (int i=1;i<=n;i++){ls[i]=0;father[i]=i;v[i]=0;in[i]=0;}for (int i=1;i<n;i++){scanf("%d%d",&x,&y);in[y]++;addl(x,y);addl(y,x);}scanf("%d%d",&q,&p);for (int i=1;i<=n;i++)//尋找根if (in[i]==0) tarjan(i);//printf("%d\n",ans);} }

網(wǎng)絡(luò)流-最大流dinic

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=10010,M=100010,inf=2147483647/3; struct node{int to,next,w; }a[M*2]; int tot=1,n,s,t,m,ans; int dep[N],ls[N]; queue<int> q; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs() {memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dep[y]&&a[i].w){dep[y]=dep[x]+1;if(y==t) return true;q.push(y);}}}return false; } int dinic(int x,int flow) {int rest=0,k;if(x==t) return flow;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow) return flow;}}if(!rest) dep[x]=0;return rest; } void netflow() {while(bfs())ans+=dinic(s,inf); } int main() {scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);}netflow();printf("%d",ans); }

網(wǎng)絡(luò)流-最小費(fèi)用最大流

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=5010,M=50010,inf=2147483647/3; struct node{int to,w,c,next; }a[M*2]; queue<int>q; int f[N],mf[N],ls[N],pre[N]; int n,s,e,tot,m,anscost,ansflow; bool v[N]; void addl(int x,int y,int w,int c) {a[++tot].w=w;a[tot].to=y;a[tot].c=c;a[tot].next=ls[x];ls[x]=tot;a[++tot].w=0;a[tot].to=x;a[tot].c=-c;a[tot].next=ls[y];ls[y]=tot; } bool spfa() {memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));memset(mf,0,sizeof(mf));q.push(s);f[s]=0;v[s]=1;mf[s]=inf;while(!q.empty()){int x=q.front();q.pop();v[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].c<f[y]&&a[i].w){f[y]=f[x]+a[i].c;mf[y]=min(mf[x],a[i].w);pre[y]=i;if(!v[y]){v[y]=true;q.push(y);}}}}return f[e]<=2147483647/3; } int updata() {int x=e;while(x!=s){a[pre[x]].w-=mf[e];a[pre[x]^1].w+=mf[e];x=a[pre[x]^1].to;}anscost+=f[e]*mf[e];ansflow+=mf[e]; } void netflow() {while(spfa())updata(); } int main() {tot=1;scanf("%d%d%d%d",&n,&m,&s,&e);for(int i=1;i<=m;i++){int x,y,w,c;scanf("%d%d%d%d",&x,&y,&w,&c);addl(x,y,w,c);}netflow();printf("%d %d",ansflow,anscost); }

---

負(fù)環(huán)

#include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=2100,M=3100; struct node{int to,next,w; }a[M*2]; queue<int> q; int n,m,tot,ls[N],f[N],cnt[N],T; bool v[N]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } bool spfa() {memset(f,0x3f,sizeof(f));memset(cnt,0,sizeof(cnt));q.push(1);cnt[1]=1;f[1]=0;v[1]=1;while(!q.empty()){int x=q.front();v[x]=0;q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;cnt[y]=cnt[x]+1;if(cnt[y]>=n&&a[i].w<0)return true;if(!v[y]){v[y]=1;q.push(y);}}} }return false; } int main() {scanf("%d",&T);while(T--){ memset(ls,0,sizeof(ls));tot=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);if(w>=0) addl(y,x,w);}if(spfa()) printf("YE5");else printf("N0");putchar('\n');} }

---

虛樹

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=110000; struct node{int to,next; }a[2*N]; int n,siz[N],dep[N],son[N],top[N],fa[N]; int tot,ls[N],p[N],ans,cnt,s[N],q,dfn[N],num; void adde(int x,int y) {if(x==y) return;a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs1(int x) {siz[x]=1;dfn[x]=++num; for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]) continue;dep[y]=dep[x]+1;fa[y]=x;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int fa) {if(son[x]){top[son[x]]=top[x];dfs2(son[x],x);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||y==son[x]) continue;top[y]=y;dfs2(y,x);} } int LCA(int x,int y) {while(top[x]!=top[y])if(dep[top[x]]<dep[top[y]]) y=fa[top[y]];else x=fa[top[x]];if(dep[x]<dep[y]) return x;return y; } void ins(int x) {if(!cnt){s[++cnt]=x;return;}int lca=LCA(s[cnt],x);while(cnt>1&&dep[lca]<dep[s[cnt-1]]){adde(s[cnt-1],s[cnt]),cnt--;}if(dep[lca]<dep[s[cnt]]) adde(lca,s[cnt--]);if((!cnt)||(s[cnt]!=lca)) s[++cnt]=lca;s[++cnt]=x; } void dp(int x) {if(siz[x]){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dp(y);if(siz[y]){siz[y]=0;ans++;}}}else{for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dp(y);siz[x]+=siz[y];siz[y]=0;}if(siz[x]>1){ans++;siz[x]=0;}}ls[x]=0; } bool cmp(int x,int y) {return dfn[x]<dfn[y];} int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);adde(x,y);adde(y,x);}dfs1(1);top[1]=1;dfs2(1,1);tot=0;memset(siz,0,sizeof(siz));memset(ls,0,sizeof(ls));scanf("%d",&q);while(q--){int k;cnt=0;ans=0;scanf("%d",&k);p[0]=1;for(int i=1;i<=k;i++){scanf("%d",&p[i]);siz[p[i]]++;}for(int i=1;i<=k;i++)if(siz[fa[p[i]]]){puts("-1");p[0]=0;break;}if(!p[0]){for(int i=1;i<=k;i++)siz[p[i]]--;continue;}sort(p+1,p+1+k,cmp);if(p[1]!=1) s[++cnt]=1;for(int i=1;i<=k;i++) ins(p[i]);while(cnt>1) adde(s[cnt-1],s[cnt]),cnt--;dp(1);siz[1]=tot=0;printf("%d\n",ans);} }

---

2-SAT

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N=2e6+10; struct node{int to,next; }a[N*2]; int n,m,tot,cnt,num,ls[N]; int dfn[N],low[N],color[N]; bool ins[N]; stack<int> S; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void tarjan(int x){dfn[x]=low[x]=++cnt;S.push(x);ins[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);else if(ins[y]) low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){++num;while(S.top()!=x){ins[S.top()]=0;color[S.top()]=num;S.pop();}color[S.top()]=num;ins[S.top()]=0;S.pop();}return; } int main() {scanf("%d%d",&n,&m);for(int k=1;k<=m;k++){int i,a,j,b;scanf("%d%d%d%d",&i,&a,&j,&b);addl(i+a*n,j+(!b)*n);addl(j+b*n,i+(!a)*n);}for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)if(color[i]==color[i+n]){printf("IMPOSSIBLE");return 0;}printf("POSSIBLE\n");for(int i=1;i<=n;i++)printf("%d ",color[i]<color[i+n]); }

Kruskal重構(gòu)樹

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; struct node{int x,y,w; }e[N]; struct edge_node{int to,next; }a[N]; int n,m,k,tot,cnt,root,ls[N],val[N]; int top[N],dep[N],siz[N],son[N],fa[N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } bool cmp(node x,node y) {return x.w<y.w;} int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void dfs1(int x) {for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]) continue;dep[y]=dep[x]+1;fa[y]=x;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;} } void dfs2(int x) {if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x]||y==son[x]) continue;top[y]=y;dfs2(y);} } int LCA(int x,int y) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}if(dep[x]<dep[y]) return x;else return y; } int main() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);for(int i=1;i<=n+m;i++)fa[i]=i;sort(e+1,e+1+m,cmp);cnt=n;for(int i=1;i<=m;i++){int fx=find(e[i].x),fy=find(e[i].y);if(fx!=fy){fa[fy]=fa[fx]=++cnt;addl(cnt,fx);addl(cnt,fy);addl(fx,cnt);addl(fy,cnt);val[cnt]=e[i].w;}}root=find(1);dfs1(root);top[root]=root;dfs2(root);for(int i=1;i<=k;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",val[LCA(x,y)]);} }

靜態(tài)仙人掌

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e4+10,K=18; struct node{int to,next,w; }a[N*2],e[N*2]; int n,m,q,tot,num,cnt; int f[N][K],s[N],val[N],dep[N],dis[N]; int ls[N],rs[N],dfn[N],low[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void adde(int x,int y,int w){e[++tot].to=y;e[tot].next=rs[x];e[tot].w=w;rs[x]=tot; } void circle(int x,int y,int w){num++;int now=y,sum=w;while(now!=f[x][0]){s[now]=sum;sum+=val[now];now=f[now][0];}sum=s[num]=s[x];s[x]=0;now=y;int Dis;while(now!=f[x][0]){Dis=min(s[now],sum-s[now]);adde(num,now,Dis);adde(now,num,Dis);now=f[now][0];}return; } void tarjan(int x){dfn[x]=low[x]=++cnt;int flag=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==f[x][0])continue;if(!dfn[y]){f[y][0]=x;val[y]=a[i].w;tarjan(y);low[x]=min(low[x],low[y]);}else low[x]=min(low[x],dfn[y]);if(low[y]<=dfn[x])continue;adde(x,y,a[i].w);adde(y,x,a[i].w);}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(x==f[y][0]||dfn[x]>=dfn[y])continue;circle(x,y,a[i].w);}return; } void dfs(int x,int fa){for(int i=rs[x];i;i=e[i].next){int y=e[i].to;if(y==fa)continue;dep[y]=dep[x]+1;dis[y]=dis[x]+e[i].w;f[y][0]=x;dfs(y,x);}return; } int Get_dis(int x,int y){int u=x,v=y;if(dep[x]>dep[y])swap(x,y);for(int i=K-1;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];int lca;if(x!=y){for(int i=K-1;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];lca=f[x][0];}else lca=x;if(lca<=n)return dis[u]+dis[v]-dis[lca]*2;else {int ans=dis[u]-dis[x]+dis[v]-dis[y];return ans+min(s[lca]-abs(s[x]-s[y]),abs(s[x]-s[y]));} } int main() {scanf("%d%d%d",&n,&m,&q);num=n;for(int i=1;i<=m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}tot=0;tarjan(1);dep[1]=1;dfs(1,0);for(int i=1;i<K;i++)for(int j=1;j<=num;j++)f[j][i]=f[f[j][i-1]][i-1]; for(int i=1;i<=q;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",Get_dis(x,y));} }

總結(jié)

以上是生活随笔為你收集整理的亿些模板【图论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。