★★☆ 输入文件：truck.in 输出文件：truck.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
【来源】
CCF全国信息学奥林匹克联赛（NOIP2013）复赛Day1
最大生成树+LCA
#include <algorithm> #include <ctype.h> #include <cstdio> #define N 20005 #define M 50005 using namespace std; void read(int &x) { x=0;char ch; for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; } struct E { int x,y,z; bool operator<(E a)const { return z>a.z; } }e[M<<1]; struct Edge { int next,to,dis; Edge (int next=0,int to=0,int dis=0) :next(next),to(to),dis(dis) {} }edge[M<<1]; bool vis[N]; int dep[N],pre[N],val[N],fa[N],dis[N],q,head[M],cnt,n,m; int find_(int x) { return fa[x]==x?x:fa[x]=find_(fa[x]); } void insert(int u,int v,int w) { edge[++cnt]=Edge(head[u],v,w); head[u]=cnt; } int min(int a,int b) {return a>b?b:a;} void dfs(int x) { vis[x]=true; for(int u=head[x];u;u=edge[u].next) { int v=edge[u].to; if(!vis[v]) { pre[v]=x; val[v]=edge[u].dis; dep[v]=dep[x]+1; dfs(v); } } } void swap(int &a,int &b) { int tmp=b; b=a; a=tmp; } int getans(int a,int b) { int min1=0x7fffffff,min2=0x7fffffff; if(dep[a]<dep[b]) swap(a,b); while(dep[a]>dep[b]) { min1=min(min1,val[a]); a=pre[a]; } while(a!=b) { min1=min(min1,val[a]); a=pre[a]; min2=min(min2,val[b]); b=pre[b]; } return min(min1,min2); } int main() { freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); read(n); read(m); for(int x,y,z,i=1;i<=m;i++) { read(e[i].x); read(e[i].y); read(e[i].z); } for(int i=1;i<=n;i++) fa[i]=i; sort(e+1,e+1+m); int num=0; for(int i=1;i<=m;i++) { int fx=find_(e[i].x),fy=find_(e[i].y); if(fx!=fy) { num++; fa[fy]=fx; insert(e[i].x,e[i].y,e[i].z); insert(e[i].y,e[i].x,e[i].z); if(num==n-1) break; } } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); read(q); for(int x,y;q--;) { read(x); read(y); int fx=find_(x),fy=find_(y); if(fx!=fy) printf("-1 "); else printf("%d ",getans(x,y)); } return 0; }