题意:给出一张无向图,有q次询问,每次给出u v两个点,求u到v时经过的权值最小的边
解法:kruskal最小生成树+LCA
#include<iostream> #include<algorithm> #define re register using namespace std; const int MAXN=10000+5,MAXM=50000+5,INF=0x7fffffff; struct kEdge{int u,v,w;}a[MAXM]; struct Edge{int next,to,dis;}e[MAXM*2]; int n,m,q,head[MAXN],f_s[MAXN],n_e=0,dep[MAXN],f[MAXN][21],val[MAXN][21]; bool vis[MAXN]; inline int fnd(int x); inline void uni(int x,int y); inline void addedge(int from,int to,int dis); int lca(int x,int y); void dfs(int x); int query(int x,int y); void kruskal(); int main() { cin>>n>>m; for(re int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].w; kruskal(); for(re int i=1;i<=n;i++) if(!vis[i]) { dep[i]=1; dfs(i); f[i][0]=i; val[i][0]=INF; } for(re int i=1;i<=20;i++) for(re int j=1;j<=n;j++) { f[j][i]=f[f[j][i-1]][i-1]; val[j][i]=min(val[j][i-1],val[f[j][i-1]][i-1]); } cin>>q; for(re int i=1;i<=q;i++) { re int u,v; cin>>u>>v; cout<<query(u,v)<<endl; } return 0; } bool cmp(const kEdge& x,const kEdge& y) { return x.w>y.w; } void kruskal() { sort(a+1,a+m+1,cmp); for(re int i=1;i<=n;i++) f_s[i]=i; for(re int i=1;i<=m;i++) { if(fnd(a[i].v)==fnd(a[i].u)) continue; addedge(a[i].u,a[i].v,a[i].w); addedge(a[i].v,a[i].u,a[i].w); uni(a[i].u,a[i].v); } } int query(int x,int y) { if(fnd(x)!=fnd(y)) return -1; return lca(x,y); } int lca(int x,int y) { int ans=INF; if(dep[x]>dep[y]) swap(x,y); for(re int i=20;i>=0;i--) if(dep[f[y][i]]>=dep[x]) { ans=min(ans,val[y][i]); y=f[y][i]; } if(x==y) return ans; for(re int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) { ans=min(ans,min(val[x][i],val[y][i])); x=f[x][i]; y=f[y][i]; } ans=min(ans,min(val[x][0],val[y][0])); return ans; } void dfs(int x) { vis[x]=1; for(re int i=head[x];i;i=e[i].next) if(!vis[e[i].to]) { dep[e[i].to]=dep[x]+1; f[e[i].to][0]=x; val[e[i].to][0]=e[i].dis; dfs(e[i].to); } } inline void uni(int x,int y) { if(fnd(x)!=fnd(y)) f_s[fnd(x)]=fnd(y); } inline int fnd(int x) { if(f_s[x]==x) return x; return f_s[x]=fnd(f_s[x]); } inline void addedge(int from,int to,int dis) { e[++n_e].next=head[from]; e[n_e].to=to; e[n_e].dis=dis; head[from]=n_e; }