正題

題目鏈接:http://www.51nod.com/Challenge/Problem.html#problemId=1743

---

題目大意

$n$個點$m$條邊的一張圖，每次詢問要求找出$x,y$直接的兩條不重路徑的最大值最小。

---

解題思路

首先第一條路徑肯定是最小生成樹上的路徑，所以我們先求出最小生成樹。

然后對與剩下的邊我們從小到大加入圖中，每條邊$(u,v)$會作為在$(u,v)$之間的所有點對的第二條路徑。也就是對與一個點對$(x,y)$中間有經過$(u,v)$的路徑那么都會取到這條邊的值，也就是將$(u,v)$這條路徑取$min$，然后詢問時就是詢問$(x,y)$之間的最大值。

而且因為是從小到大加入的，所有如果一個位置之間已經加入過就不需要管，所以我們可以開一個并查集記錄跳到最上面沒有加入的點。

時間復雜度$O(m\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10; struct node{int x,y; }e[N]; struct edge_node{int to,next; }a[N]; int n,m,q,tot,val[N],fa[N],ls[N]; int f[N][20],w[N][20],dep[N]; bool vis[N]; bool cmp(node x,node y) {return abs(val[x.x]-val[x.y])<abs(val[y.x]-val[y.y]);} int find(int x) {return (fa[x]==x)?(x):(fa[x]=find(fa[x]));} void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){if(x==341)x++,x--;f[x][0]=fa;dep[x]=dep[fa]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);}return; } int LCA(int x,int y){int ans=0;if(dep[x]>dep[y])swap(x,y);for(int i=18;i>=0;i--)if(dep[f[y][i]]>=dep[x])ans=max(ans,w[y][i]),y=f[y][i];if(x==y)return ans;for(int i=18;i>=0;i--)if(f[y][i]!=f[x][i])ans=max(ans,max(w[x][i],w[y][i])),x=f[x][i],y=f[y][i];return max(ans,max(w[x][0],w[y][0])); } int main() {scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++)scanf("%d",&val[i]),fa[i]=i;for(int i=1;i<=m;i++)scanf("%d%d",&e[i].x,&e[i].y);sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){int x=find(e[i].x),y=find(e[i].y);if(x==y)continue;addl(e[i].x,e[i].y);addl(e[i].y,e[i].x);fa[x]=y;vis[i]=1;}dfs(1,0);for(int i=1;i<=n;i++)fa[i]=i,w[i][0]=2147483647;for(int i=1;i<=m;i++){if(vis[i])continue;int x=find(e[i].x),y=find(e[i].y);while(x!=y){if(dep[x]<dep[y])swap(x,y);w[x][0]=abs(val[e[i].x]-val[e[i].y]); fa[x]=f[x][0];x=find(x);}}for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1],w[i][j]=max(w[i][j-1],w[f[i][j-1]][j-1]);while(q--){int x,y;scanf("%d%d",&x,&y);int ans=LCA(x,y);if(ans==2147483647)printf("infinitely\n");else printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的51nod1743-雪之国度【最小生成树,LCA,并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

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