想自己做网站怎么做,上海人才市场招聘,网站运营做的是什么工作,企业网站设计理念正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1743 题目大意 nnn个点mmm条边的一张图#xff0c;每次询问要求找出x,yx,yx,y直接的两条不重路径的最大值最小。 解题思路
首先第一条路径肯定是最小生成树上的路径#xff0c;所以我们先求出最小生成…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1743 题目大意
nnn个点mmm条边的一张图每次询问要求找出x,yx,yx,y直接的两条不重路径的最大值最小。 解题思路
首先第一条路径肯定是最小生成树上的路径所以我们先求出最小生成树。
然后对与剩下的边我们从小到大加入图中每条边(u,v)(u,v)(u,v)会作为在(u,v)(u,v)(u,v)之间的所有点对的第二条路径。也就是对与一个点对(x,y)(x,y)(x,y)中间有经过(u,v)(u,v)(u,v)的路径那么都会取到这条边的值也就是将(u,v)(u,v)(u,v)这条路径取minminmin然后询问时就是询问(x,y)(x,y)(x,y)之间的最大值。
而且因为是从小到大加入的所有如果一个位置之间已经加入过就不需要管所以我们可以开一个并查集记录跳到最上面没有加入的点。
时间复杂度O(mlogn)O(m\log n)O(mlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){if(x341)x,x--;f[x][0]fa;dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);}return;
}
int LCA(int x,int y){int ans0;if(dep[x]dep[y])swap(x,y);for(int i18;i0;i--)if(dep[f[y][i]]dep[x])ansmax(ans,w[y][i]),yf[y][i];if(xy)return ans;for(int i18;i0;i--)if(f[y][i]!f[x][i])ansmax(ans,max(w[x][i],w[y][i])),xf[x][i],yf[y][i];return max(ans,max(w[x][0],w[y][0]));
}
int main()
{scanf(%d%d%d,n,m,q);for(int i1;in;i)scanf(%d,val[i]),fa[i]i;for(int i1;im;i)scanf(%d%d,e[i].x,e[i].y);sort(e1,e1m,cmp);for(int i1;im;i){int xfind(e[i].x),yfind(e[i].y);if(xy)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 i1;in;i)fa[i]i,w[i][0]2147483647;for(int i1;im;i){if(vis[i])continue;int xfind(e[i].x),yfind(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];xfind(x);}}for(int j1;j18;j)for(int i1;in;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 ansLCA(x,y);if(ans2147483647)printf(infinitely\n);else printf(%d\n,ans);}return 0;
}
