并查集-按秩合并node
题目:UVA-11354ios
题目大意:给出一张n个点m条边的无向图, 每条边有一个危险度,有q个询问, 每次给出两个点s、t,找一条路, 使得路径上的最大危险度最小。web
思路:首先,咱们能够发现,若是求一个最小生成树, 那么任意两点, 在生成树上有惟一路径, 并且这条路径上的最大危险值必定最小。 可是n和q都太大, 若是直接顺着树走,每次询问最大复杂度O(n), 那么复杂度高达O(n^2),会超时。 咱们知道, 并查集在用了路径压缩以后效率高达O(n), 可是却破坏了树形结构, 因此不能用路径压缩。 然而咱们常常忽视了按秩合并这个方法, 即便不用路径压缩, 仅仅靠按秩合并, 复杂度也可低至O(logn)。 所以咱们只需按秩合并, 而后询问的时候向根回溯就好了, 复杂度mlogn。数组
注意:秩的意思就是树的高度,按秩合并事后并查集的结构为树形结构,svg
样例:ui
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1spa
此样例按秩合并事后的结构以下:code
能够看出来按秩合并事后,此并查集呈现出树形的结构,而且呈递增,所此每次访问的确定是从小到大的线路,所以路径上的最大危险度确定是最小的。。。xml
图手画的,不是很好看,还请见谅。。。。。。。blog
代码以下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m;
int pre[50000+10],ra[50000+10],vis[50000+10],e[50000+10];
struct node
{
int u,v,w;
}p[100000+10];
bool cmp(node x,node y)
{
return x.w<y.w;
}
int Find(int x)
{
return pre[x]==x?x:Find(pre[x]);
}
void Union(int a,int b,int c)
{
int x=Find(a);
int y=Find(b);
if(x==y)
return ;
if(ra[x]<ra[y])
{
pre[x]=y;
e[x]=c;//e数组记录路径上的大小
}
else
{
pre[y]=x;
e[y]=c;
if(ra[x]==ra[y])
ra[x]++;//ra数组就是记录树的高度,也就是所谓的秩
}
}
int qurey(int x,int y)//查询
{
int ans1=0,ans2=-1;
int cnt=x;//先从x往y查找,
while(true)
{
vis[cnt]=ans1;
if(cnt==pre[cnt])
break;
ans1=max(ans1,e[cnt]);
cnt=pre[cnt];
}
cnt=y;
while(true)
{
if(vis[cnt]>=0)//若是刚刚x在y下面,那么就能扫到y,这里判断一下是的话就能够直接返回了,
{
ans2=max(ans2,vis[cnt]);
break;
}
if(cnt==pre[cnt])
break;
ans2=max(ans2,e[cnt]);
cnt=pre[cnt];
}
cnt=x;
while(true)//若是x是在y上面,那刚刚x以上的树节点的vis值就被改变了,须要复原,以便下一次的查询,
{
vis[cnt]=-1;
if(cnt==pre[cnt])
break;
cnt=pre[cnt];
}
return ans2;
}
void init()
{
sort(p,p+m,cmp);
for(int i=1;i<=n;i++)
{
pre[i]=i;
ra[i]=0;
vis[i]=-1;
}
for(int i=0;i<m;i++)
{
Union(p[i].u,p[i].v,p[i].w);
}
//cout<<"pre[4]="<<pre[4]<<" "<<"pre[3]="<<pre[3]<<endl;
}
int main()
{
int kase=0;
while(cin>>n>>m)
{
if(kase)
cout<<endl;
else
kase++;
for(int i=0;i<m;i++)
cin>>p[i].u>>p[i].v>>p[i].w;
init();
int q;
cin>>q;
for(int i=0;i<q;i++)
{
int u,v;
cin>>u>>v;
cout<<qurey(u,v)<<endl;
}
}
return 0;
}