#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXM = 50000 + 10;
const int MAXN = 10000 + 10;
const int MAX = 100000 + 10;

vector<pair<int, int> > map[MAXN];
queue<int> q;
int f[MAXN][40], d[MAXN], p[MAXN], weight[MAXN][40];
bool vis[MAXN];

struct Edge{
int r, l, w;
}e[MAXM];

bool cmp(Edge a, Edge b){
return a.w >= b.w;
}

int find(int x){
if(p[x] != x)
return p[x] = find(p[x]);
return x;
}

void Kruskal(int m){
sort(&e[1], &e[1]+m, cmp);
for(int i=1; i<=m; i++){
int s = e[i].l, t = e[i].r;
if(find(s) != find(t)){
p[find(s)] = find(t);
map[e[i].l].push_back(make_pair(e[i].r, e[i].w));
map[e[i].r].push_back(make_pair(e[i].l, e[i].w));
}
}
}

void bfs(){
q.push(1);
d[1] = 1;
vis[1] = true;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0; i<map[x].size(); i++)
if(!vis[map[x][i].first]){
q.push(map[x][i].first);
vis[map[x][i].first] = true;
d[map[x][i].first] = d[x] + 1;
f[map[x][i].first][0] = x;
weight[map[x][i].first][0] = map[x][i].second;
}
}
}

void init(int n){
bfs();
for(int i=1; i<=30; i++)
for(int j=1; j<=n; j++){
f[j][i] = f[f[j][i-1]][i-1];
weight[j][i] = min(weight[j][i-1], weight[f[j][i-1]][i-1]);
}
}

void swap(int &a, int &b){
int t = a; a = b; b = t;
}

int Lca(int s, int t){
int small = MAX, tot = 0;
if(d[s] > d[t])
swap(s, t);
for(tot = 0; (1 << tot) <= d[t]; tot++);
tot--;
for(int i=tot; i>=0; i--)
if(d[t] - d[s] >= (1 << i)){
small = min(small, weight[t][i]);
t = f[t][i];
}
if(s == t)
return small;
for(int i=tot; i>=0; i--)
if(f[s][i] && f[s][i] != f[t][i]){
small = min(small, weight[s][i]);
small = min(small, weight[t][i]);
s = f[s][i];
t = f[t][i];
}
small = min(weight[s][0], small);
small = min(weight[t][0], small);
return small;
}

int main()
{
int n, m, q, x, y;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) p[i] = i;
for(int i=1; i<=m; i++)
scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].w);
Kruskal(m);
init(n);
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf("%d%d", &x, &y);
if(find(x) != find(y)){
printf("-1\n");
continue;
}
printf("%d\n", Lca(x, y));
}
return 0;
}
Kruskal + LCA倍增

P1843货车运输
Accepted

记录信息

评测状态 Accepted
题目 P1843 货车运输
递交时间 2015-08-07 15:40:51
代码语言 C++
评测机 VijosEx
消耗时间 1729 ms
消耗内存 20304 KiB
评测时间 2015-08-07 15:40:55

评测结果

编译成功

foo.cpp: In function 'void dfs(int, int)':
foo.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < line[a].size() ; i++ )
^

测试数据 #0: Accepted, time = 3 ms, mem = 19640 KiB, score = 5

测试数据 #1: Accepted, time = 15 ms, mem = 19640 KiB, score = 5

测试数据 #2: Accepted, time = 15 ms, mem = 19680 KiB, score = 5

测试数据 #3: Accepted, time = 17 ms, mem = 19688 KiB, score = 5

测试数据 #4: Accepted, time = 15 ms, mem = 19684 KiB, score = 5

测试数据 #5: Accepted, time = 15 ms, mem = 19680 KiB, score = 5

测试数据 #6: Accepted, time = 78 ms, mem = 19708 KiB, score = 5

测试数据 #7: Accepted, time = 62 ms, mem = 19700 KiB, score = 5

测试数据 #8: Accepted, time = 62 ms, mem = 19704 KiB, score = 5

测试数据 #9: Accepted, time = 62 ms, mem = 19696 KiB, score = 5

测试数据 #10: Accepted, time = 62 ms, mem = 19704 KiB, score = 5

测试数据 #11: Accepted, time = 62 ms, mem = 19700 KiB, score = 5

测试数据 #12: Accepted, time = 171 ms, mem = 20300 KiB, score = 5

测试数据 #13: Accepted, time = 171 ms, mem = 20184 KiB, score = 5

测试数据 #14: Accepted, time = 171 ms, mem = 20264 KiB, score = 5

测试数据 #15: Accepted, time = 156 ms, mem = 20244 KiB, score = 5

测试数据 #16: Accepted, time = 156 ms, mem = 20304 KiB, score = 5

测试数据 #17: Accepted, time = 140 ms, mem = 20188 KiB, score = 5

测试数据 #18: Accepted, time = 140 ms, mem = 20188 KiB, score = 5

测试数据 #19: Accepted, time = 156 ms, mem = 20200 KiB, score = 5

Accepted, time = 1729 ms, mem = 20304 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int n , m , q;
int i;
int x , y , z;
int num;

int min( int a , int b )
{
if( a > b )
return b;
return a;
}

int pre[10000 + 2];

struct linker
{
int x , y;
int z;
};

linker l[50000 + 2];

int cmp( linker a , linker b )
{
if( a.z > b.z )
return 1;
return 0;
}

int find( int x )
{
if( x == pre[x] )
return x;
pre[x] = find( pre[x] );
return pre[x];
}

void merge( int a , int b )
{
pre[ find( a ) ] = find( b );
return;
}

int fa[100000 + 2][20];
int s[100000 + 2][20];
vector < int > line[100000 + 2];
vector < int > len[100000 + 2];
bool visit[100000 + 2];
int depth[100000 + 2];

void dfs( int a , int v )
{
if( visit[a] )
return;
visit[a] = 1;
depth[a] = v;
int i;
for( i = 0 ; i < line[a].size() ; i++ )
if( !visit[ line[a][i] ] )
{
dfs( line[a][i] , v + 1 );
fa[ line[a][i] ][0] = a;
s[ line[a][i] ][0] = len[a][i];
}
return;
}

void init()
{
int i , j;
for( j = 1 ; ( 1 << j ) <= n ; j++ )
for( i = 1 ; i <= n ; i++ )
if( fa[i][j - 1] != -1 )
{
fa[i][j] = fa[ fa[i][j - 1] ][j - 1];
s[i][j] = min( s[i][j - 1] , s[ fa[i][j - 1] ][j - 1] );
}
return;
}

int lca( int a , int b )
{
if( depth[a] < depth[b] )
{
int k = a;
a = b;
b = k;
}
int dif = depth[a] - depth[b];
int i , j;
int mins = 100000000;
i = 0;
while( ( 1 << i ) <= dif )
i++;
i--;
for( j = i ; j >= 0 ; j-- )
{
if( dif >= ( 1 << j ) )
{
dif -= ( 1 << j );
mins = min( mins , s[a][j] );

a = fa[a][j];
}
if( dif == 0 )
break;
}
for( i = 0 ; ( 1 << i ) <= depth[a] ; i++ )
;
i--;
for( j = i ; j >= 0 ; j-- )
if( fa[a][j] != fa[b][j] && fa[a][j] != -1 && fa[b][j] != -1 )
{
mins = min( mins , s[a][j] );
a = fa[a][j];
mins = min( mins , s[b][j] );
b = fa[b][j];
}
if( a != b )
mins = min( mins , min( s[a][0] , s[b][0] ) );
return mins;
}

int mins;

int main()
{
memset( fa , -1 , sizeof( fa ) );
scanf( "%d %d" , &n , &m );
for( i = 0 ; i < m ; i++ )
scanf( "%d %d %d" , &l[i].x , &l[i].y , &l[i].z );
for( i = 1 ; i <= n ; i++ )
pre[i] = i;

sort( l , l + m , cmp );
for( i = 0 ; i < m ; i++ )
{
if( num == n - 1 )
break;
if( find( l[i].x ) != find( l[i].y ) )
{
merge( l[i].x , l[i].y );
num++;
line[ l[i].x ].push_back( l[i].y );
len[ l[i].x ].push_back( l[i].z );
line[ l[i].y ].push_back( l[i].x );
len[ l[i].y ].push_back( l[i].z );
}
}
dfs( 1 , 0 );
init();
scanf( "%d" , &q );
for( i = 0 ; i < q ; i++ )
{
scanf( "%d %d" , &x , &y );
mins = lca( x , y );
if( mins == 100000000 || find( x ) != find( y ) )
printf( "-1\n" );
else
printf( "%d\n" , mins );
}
return 0;
}

//蒟蒻也来贴代码

Kruskal+LCA

测试数据 #0: Accepted, time = 0 ms, mem = 1176 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 1176 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 1184 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 1180 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 1180 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 1176 KiB, score = 5
测试数据 #6: Accepted, time = 62 ms, mem = 1196 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 1196 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 1196 KiB, score = 5
测试数据 #9: Accepted, time = 62 ms, mem = 1188 KiB, score = 5
测试数据 #10: Accepted, time = 46 ms, mem = 1196 KiB, score = 5
测试数据 #11: Accepted, time = 62 ms, mem = 1188 KiB, score = 5
测试数据 #12: Accepted, time = 249 ms, mem = 1552 KiB, score = 5
测试数据 #13: Accepted, time = 234 ms, mem = 1492 KiB, score = 5
测试数据 #14: Accepted, time = 218 ms, mem = 1536 KiB, score = 5
测试数据 #15: Accepted, time = 218 ms, mem = 1528 KiB, score = 5
测试数据 #16: Accepted, time = 234 ms, mem = 1564 KiB, score = 5
测试数据 #17: Accepted, time = 187 ms, mem = 1488 KiB, score = 5
测试数据 #18: Accepted, time = 156 ms, mem = 1484 KiB, score = 5
测试数据 #19: Accepted, time = 156 ms, mem = 1496 KiB, score = 5
Accepted, time = 2068 ms, mem = 1564 KiB, score = 100

###Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define MAXN 10005
#define MAXM 50005
#define MAXQ 30005
int N,M,Q;
int U,V,W;
int src,child,ans,d1,d2;
int head[MAXN];
int vis[MAXN],fa[MAXN],depth[MAXN],weight[MAXN];
vector<pair<int,int> > v[MAXN];

struct edge
{
int u,v,w;

edge() {}
edge(int _u,int _v,int _w) { u=_u,v=_v,w=_w;}
}e[MAXM];

bool cmp(const edge &e1,const edge &e2) { return e1.w>e2.w;}

int find(int x)
{
if(head[x]==x) return x;

return head[x]=find(head[x]);
}

void Kruskal()
{
int cnt=0;
for(int i=1;i<=M;i++)
{
U=e[i].u, V=e[i].v, W=e[i].w;
if(find(U)!=find(V))
{
v[U].push_back(make_pair(V,W));
v[V].push_back(make_pair(U,W));
cnt++;
head[find(U)]=find(V);

}
if(cnt==N-1) break;

}

}

void BFS(int start)
{
queue<int> q;
q.push(start);
vis[start]=1;
while(!q.empty())
{
src=q.front();
q.pop();
for(int i=0;i<v[src].size();i++)
{
child=v[src][i].first;
if(!vis[child])
{
vis[child]=1;
q.push(child);

fa[child]=src;
depth[child]=depth[src]+1;
weight[child]=v[src][i].second;
}
}

}

}

int LCA(int i,int j)
{
ans=INT_MAX;
d1=depth[i], d2=depth[j];
while(i!=j)
{

if(d1>d2)
{
ans=min(ans,weight[i]);
i=fa[i], d1--;
}
else
{
ans=min(ans,weight[j]);
j=fa[j], d2--;
}
}
return ans;
}

int main()
{
cin>>N>>M;
for(int _u,_v,_w,i=1;i<=M;i++)
{
scanf("%d%d%d",&_u,&_v,&_w);
e[i]=edge(_u,_v,_w);
}
for(int i=1;i<=N;i++) head[i]=i;
sort(e+1,e+1+M,cmp);
Kruskal();
for(int i=1;i<=N;i++)
if(head[i]==i) BFS(i);
cin>>Q;
for(int s,t,i=1;i<=Q;i++)
{
scanf("%d%d",&s,&t);
if(find(s)!=find(t)) printf("-1\n");
else printf("%d\n",LCA(s,t));
}
system("pause");
return 0;
}

用stl algorithm排序的注意,请用stable_sort(),或者使用"<"">"而不是"<="">="来写比较函数,避免在#15RE
(stable_sort大法好)

嗯……这个要使路径上最小边权最大，所以一定是在最大生成树（森林）上找（反证法：如果能在最大生成树以外另找出一条路径，且这条路径上最小边权更大一些，则原来的树必然不是最大生成树）
非常轻松愉快的Kruskal求出最大生成树（森林）
然后用倍增法求lca：同时维护p[i][j]和dist[i][j]，分别表示第i个点的2^j祖先,及从第i个点走到它的2^j祖先这条路径上的最小边权。

我WA的原因：1.倍增爬树的时候应该先算ans：min(ans,dist[x][i])后更新x的位置：x-->p[x][i]
2.在求Kruskal的时候用过fa数组了，然后在求LCA的时候我又重新初始化，但是这个时 候就不能初始化为0了，而应该是fa[i]=i
希望我犯的错误能给大家一些提示……嗯……如果有用的话也请留个言吧~也让我更有动力继续写题解

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define r(i,j,n) for(int i=j;i<=n;++i)
#define pb push_back
using namespace std;
const int N=10010;

struct edge{
int from,to,v;
bool operator < (const edge& now)const{
return v>now.v;
}
};

vector<edge>E,G[N];
int n,m;
void init()
{
scanf("%d%d",&n,&m);
int x,y,z;
rep(i,m){
scanf("%d%d%d",&x,&y,&z);
E.pb((edge){x,y,z});
}
}

int fa[N];
int getfather(int x)
{
if(x==fa[x]) return x;
else fa[x]=getfather(fa[x]);
return fa[x];
}

int d[N],p[N][20],dist[N][20];

void dfs(int x,int deep)
{
d[x]=deep;
rep(i,G[x].size())
if (!d[G[x][i].to]) {
dfs(G[x][i].to,deep+1);
fa[G[x][i].to]=x;
p[G[x][i].to][0]=x;
dist[G[x][i].to][0]=G[x][i].v;
}
}

void ST()
{
for(int j=1;(1<<j)<=n;++j)
r(i,1,n)
if (p[i][j-1]!=-1){
p[i][j]=p[p[i][j-1]][j-1];
dist[i][j]=min(dist[i][j-1],dist[p[i][j-1]][j-1]);
}
}

int LCA(int x,int y)
{
if (getfather(x)!=getfather(y)) return -1;
int ans=1000000000;
if (d[x]<d[y]) swap(x,y);
int k=log(d[x])/log(2);
for(int i=k;i>=0;--i)
if(d[x]-(1<<i)>=d[y]) {ans=min(ans,dist[x][i]);x=p[x][i];}
if (x==y) return ans;
for(int i=k;i>=0;--i)
if(p[x][i]!=-1 && p[x][i]!=p[y][i]) {
ans=min(ans,min(dist[x][i],dist[y][i]));
x=p[x][i];
y=p[y][i];
}
ans=min(ans,min(dist[x][0],dist[y][0]));
if(p[x][0]==0) ans=-1;
if (ans==1000000000) ans=-1;
return ans;
}

void solve()
{
sort(E.begin(),E.end());
int num=0;
r(i,1,n) fa[i]=i;
rep(i,E.size()){
int f1=getfather(E[i].from),f2=getfather(E[i].to);
if (f1!=f2){
fa[f1]=f2;
G[E[i].from].pb(E[i]);
// cout <<E[i].from<<" "<<E[i].to<<" "<<E[i].v<<endl;
G[E[i].to].pb((edge){E[i].to,E[i].from,E[i].v});
num++;
if (num==n-1) break;
}
}

memset(p,-1,sizeof p);
memset(dist,63,sizeof dist);
memset(d,0,sizeof d);
r(i,1,n) fa[i]=i;
r(i,1,n) if (!d[i]) dfs(i,1);
// r(i,1,n) {printf("d[%d]=%d",i,d[i]);cout <<endl;}
ST();
int q,x,y;
scanf("%d",&q);
rep(i,q){
scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
}
int main()
{
// freopen("truck.in","r",stdin);
// freopen("truck.out","w",stdout);
init();
solve();
return 0;
}

type
TEdge = record
x, y: longint;
weight: longint;
end;

operator <(x, y: TEdge)res: Boolean;
begin
res := (x.weight<y.weight);
end;

var
edges: array [1..50000] of TEdge;
n, m: longint;

procedure sort(l, r: longint);
var
i, j: longint;
m, t: TEdge;
begin
i := l;
j := r;
m := edges[(i+j)>>1];
repeat
while m<edges[i] do inc(i);
while edges[j]<m do dec(j);
if i<=j then
begin
t := edges[i];
edges[i] := edges[j];
edges[j] := t;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i, r);
if l<j then sort(l, j);
end;

var
sets: array [1..10000] of longint;
map: array [1..10000, 1..10000] of longint;

var
head: array [1..10000] of longint;
nedges: array [1..20000] of record
weight : longint;
y: longint;
next: longint;
end;
tot: longint;

procedure addedge(x, y: longint; weight: longint);
begin
inc(tot);
nedges[tot].next := head[x];
nedges[tot].weight := weight;
nedges[tot].y := y;
head[x] := tot;
map[x, y] := weight;
end;

function find(x: longint): longint;
begin
if x = sets[x] then
exit(x);
sets[x] := find(sets[x]);
exit(sets[x]);
end;

function combine(x, y: longint): Boolean;
var
tx, ty: longint;
begin
tx := find(x);
ty := find(y);
if tx = ty then
exit(false);
sets[tx] := ty;
exit(true);
end;

procedure kruscal;
var
i: longint;
begin
sort(1, m);
for i := 1 to n do
sets[i] := i;
tot := 0;
for i := 1 to m do
if combine(edges[i].x, edges[i].y) then
begin
addedge(edges[i].x, edges[i].y, edges[i].weight);
addedge(edges[i].y, edges[i].x, edges[i].weight);
end;
end;

var
depth: array [1..10000] of longint;
father: array [1..10000, 0..16] of longint;
dp: array [1..10000, 0..16] of longint;

function min(x, y: longint): longint;
begin
if x<y then exit(x) else exit(Y);
end;

procedure dfs(x: longint);
var
i, j: longint;
begin
depth[x] := depth[father[x][0]]+1;
j := 1;
if map[x][father[x][0]]=0 then
map[x][father[x][0]] := maxlongint;

dp[x][0] := map[x][father[x][0]];
while 1<<j<=depth[x]-1 do
begin
father[x][j] := father[father[x][j-1]][j-1];
dp[x][j] := min(dp[x][j-1], dp[father[x][j-1]][j-1]);
inc(j);
end;

i := head[x];
while i<>0 do
begin
if nedges[i].y = father[x][0] then
begin
i := nedges[i].next;
continue;
end;
father[nedges[i].y][0] := x;
dfs(nedges[i].y);
i := nedges[i].next;
end;
end;

function lca(x, y: longint): longint;
var
t, i, j: longint;
begin
if depth[x]<depth[y] then
begin
t := x; x := y; y := t;
end;

t := depth[x] - depth[y];
j := 0;
while 1<<j<=t do
begin
if t and (1<<j) <> 0 then
x := father[x][j];
inc(j);
end;
if x = y then exit(x);
for j := 16 downto 0 do
if father[x][j] <> father[y][j] then
begin
x := father[x][j];
y := father[y][j];
end;

exit(father[x][0]);
end;

function calc(x, y: longint): longint; // x is child of y
var
t, j: longint;
begin
t := depth[x] - depth[y];
j := 0;
calc := maxlongint;
while x<>y do
begin
if t and (1<<j) <> 0 then
begin
calc := min(calc, dp[x][j]);
x := father[x][j];
end;
inc(j);
end;
end;

var
i, t, x, y: longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(n, m);
for i :=1 to m do
read(edges[i].x, edges[i].y, edges[i].weight);

kruscal;
for i := 1 to n do
begin
if father[i][0]<>0 then continue;
father[i][0] := i;
dfs(i);
end;
read(m);
for i := 1 to m do
begin
read(x, y);
if find(x) <> find(y) then
writeln(-1)
else
begin
t := lca(x, y);
writeln(min(calc(x, t), calc(y, t)));
end;
end;

close(input); close(output);
end.

program pro;
var
fat:array[0..15000,0..20]of record po,pr:longint; end;
st,deep,f,maxx:array[0..15000]of longint;
link:array[0..50000]of record ke,po,ne,pr:longint; end;
road:array[0..50000]of record a,b,co:longint; end;
n,m,tot,i,j:longint;

function min(x,y:longint):longint;
begin
if x>y then exit(y)
else exit(x);
end;

function max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;

procedure swap(var x,y:longint);
var
kk:longint;
begin
kk:=x;
x:=y;
y:=kk;
end;

procedure make(u,v,c:longint);
begin
inc(tot);
link[tot].ne:=st[u];
st[u]:=tot;
link[tot].ke:=u;
link[tot].po:=v;
link[tot].pr:=c;
end;

procedure qsort(l,r:longint);
var
ii,jj,mid:longint;
begin
ii:=l; jj:=r; mid:=road[(ii+jj)shr 1].co;
repeat
while (road[ii].co>mid) do inc(ii);
while (road[jj].co<mid) do dec(jj);
if ii<=jj then
begin
swap(road[ii].a,road[jj].a);
swap(road[ii].b,road[jj].b);
swap(road[ii].co,road[jj].co);
inc(ii); dec(jj);
end;
until ii>jj;
if ii<r then qsort(ii,r);
if jj>l then qsort(l,jj);
end;

function getf(x:longint):longint;
begin
if f[x]=x then exit(x)
else f[x]:=getf(f[x]);
getf:=f[x];
end;

function union(num:longint):boolean;
var
x,y,z:longint;
begin
x:=road[num].a;
y:=road[num].b;
z:=road[num].co;
x:=getf(x); y:=getf(y);
if x=y then exit(false);
f[y]:=x;
make(road[num].a,road[num].b,road[num].co);
make(road[num].b,road[num].a,road[num].co);
exit(true);
end;

procedure ready(x:longint;pa:longint);
var
temp,son,po,ii:longint;
begin
temp:=st[x];
while temp<>0 do
begin
if link[temp].po<>pa then
begin
son:=link[temp].po;
po:=x;
deep[son]:=deep[po]+1;
fat[son,0].po:=po;
fat[son,0].pr:=link[temp].pr;
ii:=0;
while (fat[po,ii].po<>0) do
begin
fat[son,ii+1].po:=fat[po,ii].po;
fat[son,ii+1].pr:=min(fat[son,ii].pr,fat[po,ii].pr);
po:=fat[po,ii].po;
inc(ii);
end;
ready(son,x);
end;
temp:=link[temp].ne;
end;
end;

function find(x,y:longint):longint;
var
ans,temp,dis,po,son,fa,ii:longint;
begin
if getf(x)<>getf(y) then exit(-1);
ans:=maxlongint;
if deep[x]<deep[y] then swap(x,y);
dis:=deep[x]-deep[y];
ii:=0;
while dis>0 do
begin
if dis and 1=1 then
begin
if fat[x,ii].pr<>0 then ans:=min(ans,fat[x,ii].pr);
x:=fat[x,ii].po;
end;
dis:=dis shr 1;
if (dis<>0)and(fat[x,ii].pr<>0) then ans:=min(ans,fat[x,ii].pr);
inc(ii);
end;

if x=y then exit(ans);

ii:=0;
while x<>y do
begin
if (fat[x,ii].po<>fat[y,ii].po)or((fat[x,ii].po=fat[y,ii].po)and(ii=0)) then
begin
ans:=min(ans,fat[x,ii].pr);
ans:=min(ans,fat[y,ii].pr);
x:=fat[x,ii].po; y:=fat[y,ii].po;
inc(ii);
end
else dec(ii);
end;
exit(ans);
end;

procedure init;
var
u,v,c,ii,jj:longint;
begin
readln(n,m);
tot:=0;
for ii:=1 to m do readln(road[ii].a,road[ii].b,road[ii].co);
end;

procedure main;
var
u,v,q,tot,ii,jj:longint;
begin
qsort(1,m);
for ii:=1 to n do f[ii]:=ii;
tot:=1;
for ii:=1 to m do
if union(ii) then
begin
inc(tot);
if tot=n then break;
end;
ready(1,0);
readln(q);
for ii:=1 to q do
begin
readln(u,v);
writeln(find(u,v));
end;
end;

begin
init;
main;
end.

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<list>
#include<queue>
using namespace std;
bool intree[10002]={0},group[10002]={0};
int n,m,x,y,z,q,id[10002],sz[10002],f[10002][19]={0},d[10002]={0},g[10002][19]={0},deep=0,deep2,ans=0x7fffffff;
struct e
{
int x,y,z;
bool use;
bool operator<(const e&A)const
{
return z>A.z;
}
}eg[50002]={0,0,0,0};
list<int>son[10002],sonv[10002];
queue<int,list<int> >que;
int find(int p)
{
while(p!=id[p])
{
id[p]=id[id[p]];
p=id[p];
}
return p;
}
void link(int a,int b)
{
int ar=find(a),br=find(b);
if(ar!=br)
{
if(sz[ar]<sz[br])
{
sz[br]+=sz[ar];
id[ar]=id[br];
}
else
{
sz[ar]+=sz[br];
id[br]=id[ar];
}
}
}
int dfs(int p)
{
if(d[p])
return d[p];
else
{
d[p]=dfs(f[p][0])+1;
return d[p];
}
}
void lca(int a,int b)
{
int h,i;
if(d[a]!=d[b])
if(d[a]>d[b])
{
h=d[a]-d[b];
for(i=deep2;i>=0;i--)
if(h&(1<<i))
{
ans=min(ans,g[a][i]);
a=f[a][i];
}
}
else
{
h=d[b]-d[a];
for(i=deep2;i>=0;i--)
if(h&(1<<i))
{
ans=min(ans,g[b][i]);
b=f[b][i];
}
}
for(i=deep2;i>=0;i--)
if(f[a][i]&&f[b][i])
if(f[a][i]!=f[b][i])
{
ans=min(ans,min(g[a][i],g[b][i]));
lca(f[a][i],f[b][i]);
return;
}
if(a!=b)
{
if(g[a][0])
ans=min(ans,g[a][0]);
if(g[b][0])
ans=min(ans,g[b][0]);
}
}
main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
id[i]=i;
sz[i]=1;
}
for(i=0;i<m;i++)
scanf("%d%d%d",&eg[i].x,&eg[i].y,&eg[i].z);
sort(eg,eg+m);
for(i=0;i<m;i++)
if(find(eg[i].x)!=find(eg[i].y))
{
link(eg[i].x,eg[i].y);
eg[i].use=1;
son[eg[i].x].push_back(eg[i].y);
sonv[eg[i].x].push_back(eg[i].z);
son[eg[i].y].push_back(eg[i].x);
sonv[eg[i].y].push_back(eg[i].z);
}
for(i=1;i<=n;i++)
{
group[find(i)]=1;
d[find(i)]=1;
}
for(i=1;i<=n;i++)
if(group[i])
{
que.push(i);
while(!que.empty())
{
x=que.front();
que.pop();
intree[x]=1;
for(list<int>::iterator j=son[x].begin(),s=sonv[x].begin();j!=son[x].end();j++,s++)
if(!intree[*j])
{
y=*j;
intree[y]=1;
f[y][0]=x;
g[y][0]=*s;
que.push(y);
}
}
}
for(i=1;i<=n;i++)
{
if(!d[i])
dfs(i);
deep=max(deep,d[i]);
}
deep2=log(deep)/log(2);
for(j=1;j<=deep2;j++)
for(i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&x,&y);
if(find(x)!=find(y))
printf("-1\n");
else
{
ans=0x7fffffff;
lca(x,y);
printf("%d\n",ans);
}
}
}

#include<cstdio>
#include<list>
#include<queue>
#include<cmath>
#include<algorithm>
#define IOFileName "P1843"
using namespace std;
const int maxn=10002,maxm=50002,maxdeep2=19;

//#define debug
//#define IOwithfile

int n,m,x,y,z,q;
struct edge{
int x,y,z;
bool use;
bool operator<(const edge &A)const{
return z>A.z;
}
}eg[maxm]={0,0,0,false};
int id[maxn],sz[maxn];
list<int>son[maxn],sonv[maxn];
queue<int,list<int> >que;
bool intree[maxn]={false},group[maxn]={false};
int f[maxn][maxdeep2]={0},d[maxn]={0},g[maxn][maxdeep2]={0};
int deep=0,deep2,ans=0x7fffffff;

int find(int p){
while(p!=id[p]){
id[p]=id[id[p]];
p=id[p];
}
return p;
}
void link(int a,int b){
int ar=find(a),br=find(b);
if(ar!=br){
if(sz[ar]<sz[br]){
sz[br]+=sz[ar];
id[ar]=id[br];
}else{
sz[ar]+=sz[br];
id[br]=id[ar];
}
}
}

int dfs(int p){
if(d[p]){
return d[p];
}else{
d[p]=dfs(f[p][0])+1;
return d[p];
}
}

void lca(int a,int b){
#ifdef debug
printf("a=%d b=%d\n",a,b);
#endif
if(d[a]!=d[b]){
if(d[a]>d[b]){
int h=d[a]-d[b];
for(int i=deep2;i>=0;i--){

if(h&(1<<i)){
ans=min(ans,g[a][i]);
#ifdef debug
printf(" ans=%d\n",ans);
#endif
a=f[a][i];
}
#ifdef debug
printf(" a=%d b=%d i=%d\n",a,b,i);
#endif
}
}else{
int h=d[b]-d[a];
for(int i=deep2;i>=0;i--){

if(h&(1<<i)){
ans=min(ans,g[b][i]);
#ifdef debug
printf(" ans=%d\n",ans);
#endif
b=f[b][i];
}
#ifdef debug
printf(" a=%d b=%d i=%d\n",a,b,i);
#endif
}
}
}
#ifdef debug
printf("a=%d b=%d\n",a,b);
#endif
for(int i=deep2;i>=0;i--){
if(f[a][i]&&f[b][i]){
if(f[a][i]!=f[b][i]){
ans=min(ans,min(g[a][i],g[b][i]));
lca(f[a][i],f[b][i]);
return;
}
}
}
if(a!=b){
if(g[a][0]){
ans=min(ans,g[a][0]);
}
if(g[b][0]){
ans=min(ans,g[b][0]);
}
}
}

int main(){
#ifdef IOwithfile
freopen(IOFileName".in","r",stdin);
freopen(IOFileName".out","w",stdout);
#endif

scanf("%d %d\n",&n,&m);
for(int i=1;i<=n;i++){
id[i]=i;
sz[i]=1;
}
for(int i=0;i<m;i++){
scanf("%d %d %d\n",&eg[i].x,&eg[i].y,&eg[i].z);
}
sort(eg,eg+m);
for(int i=0;i<m;i++){
if(find(eg[i].x)!=find(eg[i].y)){
link(eg[i].x,eg[i].y);
eg[i].use=true;
son[eg[i].x].push_back(eg[i].y);
sonv[eg[i].x].push_back(eg[i].z);
son[eg[i].y].push_back(eg[i].x);
sonv[eg[i].y].push_back(eg[i].z);
}
}
#ifdef debug
for(int i=0;i<m;i++){
printf("eg[%d]={%d,%d,%d,%d}\n",i,eg[i].x,eg[i].y,eg[i].z,eg[i].use);
}
for(int i=1;i<=n;i++){
printf("son[%d]=",i);
for(list<int>::iterator j=son[i].begin();j!=son[i].end();j++){
printf("%d ",*j);
}
printf("\n");
}
#endif
for(int i=1;i<=n;i++){
group[find(i)]=true;
d[find(i)]=1;
}
#ifdef debug
for(int i=1;i<=n;i++){
printf("group[%d]=%d\n",i,group[i]);
}
#endif
for(int i=1;i<=n;i++){
if(group[i]){
que.push(i);
while(!que.empty()){
x=que.front();
que.pop();
intree[x]=true;
for(list<int>::iterator j=son[x].begin(),s=sonv[x].begin();j!=son[x].end();j++,s++){
if(!intree[*j]){
y=*j;
intree[y]=true;
f[y][0]=x;
g[y][0]=*s;
que.push(y);
}
}
}
}
}
#ifdef debug
for(int i=1;i<=n;i++){
printf("f[%d][0]=%d g[%d][0]=%d\n",i,f[i][0],i,g[i][0]);
}
#endif
for(int i=1;i<=n;i++){
if(!d[i]){
dfs(i);
}
deep=max(deep,d[i]);
}
deep2=log(deep)/log(2);
#ifdef debug
for(int i=1;i<=n;i++){
printf("d[%d]=%d\n",i,d[i]);
}
printf("deep=%d deep2=%d\n",deep,deep2);
#endif
for(int j=1;j<=deep2;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);
}
}
#ifdef debug
for(int i=1;i<=n;i++){
printf("f[%d]=",i);
for(int j=0;j<=18;j++){
printf("%d ",f[i][j]);
}
printf("\n");
}
for(int i=1;i<=n;i++){
printf("g[%d]=",i);
for(int j=0;j<=18;j++){
printf("%d ",g[i][j]);
}
printf("\n");
}
#endif
scanf("%d\n",&q);
for(int i=0;i<q;i++){
scanf("%d %d\n",&x,&y);
#ifdef debug
printf("x=%d y=%d\n",x,y);
#endif
if(find(x)!=find(y)){
printf("-1\n");
}else{
ans=0x7fffffff;
lca(x,y);
printf("%d\n",ans);
}
}
}

1894ms+4344KiB
235行超详细debug，对拍除错专用，值得拥有！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=10000+19,M=50000+19,oo=(1<<30)-1;
struct Edge
{
int x,y,z,nxt;
bool operator < (const Edge& B) const {return z>B.z;}
} E[M],_E[N*2];
int n,m,Q,x,y,z;
int cnt,Last[N],Fa[N][21],Min[N][21],Pa[N],Deep[N];

inline void Add_Edge(int x,int y,int z) {_E[cnt]=(Edge){x,y,z,Last[x]};Last[x]=cnt++;}
inline int Getf(int x) {return Pa[x]==x?x:Pa[x]=Getf(Pa[x]);}
inline void DFS(int x)
{
for (int i=Last[x];i^-1;i=_E[i].nxt)
{
int y=_E[i].y;
if (y==Fa[x][0]) continue;
Fa[y][0]=x;Min[y][0]=_E[i].z;Deep[y]=Deep[x]+1;
DFS(y);
}
}
inline int Solve(int x,int y)
{
if (x==y) return 0;
if (Deep[x]<Deep[y]) swap(x,y);
int Ans=oo;
for (int i=20;i>=0;i--)
if (Deep[Fa[x][i]]>Deep[y]) Ans=min(Ans,Min[x][i]),x=Fa[x][i];
if (Deep[x]>Deep[y]) Ans=min(Ans,Min[x][0]),x=Fa[x][0];
if (x==y) return Ans;
for (int i=20;i>=0;i--)
if (Fa[x][i]^Fa[y][i])
{
Ans=min(Ans,min(Min[x][i],Min[y][i]));
x=Fa[x][i];y=Fa[y][i];
}
return min(Ans,min(Min[x][0],Min[y][0]));
}

int main()
{
memset(Last,-1,sizeof(Last));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) Pa[i]=i;
for (int i=0;i<m;i++) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].z);
sort(E,E+m);
for (int i=0;i<m;i++)
{
int Fx=Getf(E[i].x),Fy=Getf(E[i].y);
if (Fx^Fy)
{
Pa[Fx]=Fy;
Add_Edge(E[i].x,E[i].y,E[i].z);
Add_Edge(E[i].y,E[i].x,E[i].z);
}
}
for (int i=1;i<=n;i++) if (!Fa[i][0]) DFS(i);
for (int i=1;i<=20;i++)
for (int x=1;x<=n;x++)
{
Min[x][i]=min(Min[x][i-1],Min[Fa[x][i-1]][i-1]);
Fa[x][i]=Fa[Fa[x][i-1]][i-1];
}
scanf("%d",&Q);
while (Q--)
{
scanf("%d%d",&x,&y);
if (Getf(x)^Getf(y)) {printf("-1\n");continue;}
printf("%d\n",Solve(x,y));
}
}

MST按秩合并，直接暴力LCA

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge
{
    int u,v,limit;
    inline void Read()
    {
        scanf("%d%d%d",&u,&v,&limit);
    }
}Sed[50004];
int son[10004];
struct Edge2
{
    int link,next,limit;
}ed[50004];
int Ecnt;
inline void Add(int u,int v,int l)
{
    ed[++Ecnt].link=v,ed[Ecnt].limit=l,ed[Ecnt].next=son[u];
    son[u]=Ecnt;
}
int f[10004],h[10004],d[10004],fa[10004],ll[10004];
int getf(int x)
{
    if (f[x]==x) return x;
    return f[x]=getf(f[x]);
}
void Get_Dep(int x,int dep)
{
    d[x]=dep;
    for (int i=son[x];i;i=ed[i].next) Get_Dep(ed[i].link,dep+1),fa[ed[i].link]=x,ll[ed[i].link]=ed[i].limit;
}
const int INF=~0U>>4;
int Get_Ans(int u,int v)                         //LCA
{
    int x=u,y=v,ans=INF;
    while (x!=y)
    {
        if (d[x]<d[y]) y=fa[y];
        else if (d[x]>d[y]) x=fa[x];
        else x=fa[x],y=fa[y];
    }
    while (u!=x) ans=min(ans,ll[u]),u=fa[u];
    while (v!=y) ans=min(ans,ll[v]),v=fa[v];
    return ans;
}
inline bool cmp(const Edge& A,const Edge& B)
{
    return A.limit>B.limit;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        Sed[i].Read();
    for (int i=1;i<=n;i++)
        h[i]=0,f[i]=i;
    sort(Sed+1,Sed+m+1,cmp);
    for (int i=1;i<=m;i++)           //构树
    {
        Edge x=Sed[i];
        int u=getf(x.u),v=getf(x.v);
        if (u==v) continue;
        if (h[u]>h[v]) Add(u,v,x.limit),f[f[v]]=u;
        else if (h[u]<h[v]) Add(v,u,x.limit),f[f[u]]=v;
        else Add(u,v,x.limit),h[u]++,f[f[v]]=u;
    }
    for (int i=1;i<=n;i++)
        if (f[i]==i) Get_Dep(i,1);
    int q;
    scanf("%d",&q);
    for (int i=1,u,v;i<=q;i++)
    {
        scanf("%d%d",&u,&v);
        if (getf(u)!=getf(v))
        {
            puts("-1");
            continue;
        }
        printf("%d\n",Get_Ans(u,v));
    }
    return 0;
}

MST跑出最大森林,做一下数组标记,最后询问的时候判断一下
在一个生成树里的就用倍增LCA求一下答案
代码好长,但是写起来比较清晰
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 20580 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 20576 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 20580 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 20580 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 20580 KiB, score = 5
测试数据 #5: Accepted, time = 31 ms, mem = 20580 KiB, score = 5
测试数据 #6: Accepted, time = 46 ms, mem = 20580 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 20576 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 20580 KiB, score = 5
测试数据 #9: Accepted, time = 31 ms, mem = 20580 KiB, score = 5
测试数据 #10: Accepted, time = 46 ms, mem = 20580 KiB, score = 5
测试数据 #11: Accepted, time = 46 ms, mem = 20576 KiB, score = 5
测试数据 #12: Accepted, time = 109 ms, mem = 20580 KiB, score = 5
测试数据 #13: Accepted, time = 109 ms, mem = 20576 KiB, score = 5
测试数据 #14: Accepted, time = 93 ms, mem = 20580 KiB, score = 5
测试数据 #15: Accepted, time = 78 ms, mem = 20580 KiB, score = 5
测试数据 #16: Accepted, time = 109 ms, mem = 20580 KiB, score = 5
测试数据 #17: Accepted, time = 62 ms, mem = 20584 KiB, score = 5
测试数据 #18: Accepted, time = 93 ms, mem = 20580 KiB, score = 5
测试数据 #19: Accepted, time = 78 ms, mem = 20580 KiB, score = 5
Accepted, time = 1099 ms, mem = 20584 KiB, score = 100
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define MAX 100010
using namespace std;

struct Complex{
int x,y;
int len;
}edge[MAX];

int points,edges;
int father[MAX];
int belong[MAX];
bool v[MAX];
int total_tree;
int head[MAX],total;
int _next[MAX],aim[MAX],length[MAX];
int deep[MAX];
int table[MAX][20],table_length[MAX][20];
int length_to_father[MAX];

bool cmp(Complex a,Complex b);
int Find(int x);
void Add(int x,int y,int len);
void FloodFill(int x,int flag,int step,int last);
void Initialize();
int GetLCA(int x,int y);

int main()
{
cin>>points>>edges;
for(int i=1;i<=edges;i++)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
sort(edge+1,edge+edges+1,cmp);
for(int i=1;i<=points;i++) father[i]=i;
for(int i=1;i<=edges;i++){
int fx=Find(edge[i].x);
int fy=Find(edge[i].y);
if(fx!=fy){
father[fx]=fy;
Add(edge[i].x,edge[i].y,edge[i].len);
Add(edge[i].y,edge[i].x,edge[i].len);
}
}
memset(father,0,sizeof(father));
for(int i=1;i<=points;i++)
if(!v[i])
FloodFill(i,++total_tree,1,0);
Initialize();
int asks;
cin>>asks;
for(int x,y,i=1;i<=asks;i++){
scanf("%d%d",&x,&y);
printf("%d\n",belong[x]==belong[y]?GetLCA(x,y):-1);
}
return 0;
}

bool cmp(Complex a,Complex b)
{
return a.len>b.len;
}

int Find(int x)
{
if(father[x]==x)
return father[x];
return father[x]=Find(father[x]);
}

void Add(int x,int y,int len)
{
_next[++total]=head[x];
aim[total]=y;
length[total]=len;
head[x]=total;
}

void FloodFill(int x,int flag,int step,int last)
{
v[x]=true;
belong[x]=flag;
deep[x]=step;
for(int i=head[x];i;i=_next[i])
{
if(aim[i]==last) continue;
father[aim[i]]=x;
length_to_father[aim[i]]=length[i];
FloodFill(aim[i],flag,step+1,x);
}
}

void Initialize()
{
for(int i=1;i<=points;i++){
table[i][0]=father[i];
table_length[i][0]=length_to_father[i];
}
for(int j=1;j<20;j++)
for(int i=1;i<=points;i++){
table[i][j]=table[table[i][j-1]][j-1];
table_length[i][j]=min(table_length[i][j-1],table_length[table[i][j-1]][j-1]);
}
}

int GetLCA(int x,int y)
{
int re=0x7f7f7f7f;
if(deep[x]<deep[y])
swap(x,y);
for(int i=19;i>=0;i--)
if(deep[table[x][i]]>=deep[y]){
re=min(re,table_length[x][i]);
x=table[x][i];
}
for(int i=19;i>=0;i--)
if(table[x][i]!=table[y][i])
{
re=min(re,table_length[x][i]);
re=min(re,table_length[y][i]);
x=table[x][i],y=table[y][i];
}
if(x!=y){
re=min(re,table_length[x][0]);
re=min(re,table_length[y][0]);
}
return re;
}

Link/Cut Tree练习题……
（这题根本不用动态树好吗！！）
先Kruskal求出最大生成森林，然后查询的时候并查集判连通性，不在一棵树里就输出-1，否则在LCT里乱Expose……
代码写得太渣就不贴了……

这题有个(m+q)sqrt(q)的算法，比较好写：
1. 按顺序合并结点，每合并sqrt(q)次的时候检查一下所有的询问。复杂度msqrt(q).
这样知道了每个询问的答案的大概范围(误差不超过sqrt(q))
2. 重新再按顺序合并结点，每次合并都检查答案可能是当前边的那些询问。复杂度qsqrt(q)
(因为每个询问最多被处理sqrt(q)次)

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

int n, m, q;

struct edge
{
int a, b;
int w;
bool operator <(edge that)const
{
return w > that.w;
}
}E[1000001];

int F[1000001];
int f(int w){return F[w] == w ? w : F[w] = f(F[w]);}
int qA[1000001], qB[1000001];
int ans[1000001];

int BOUND = 200;
vector <int> thisPeroid[1000001];

int MAIN()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
cin >> E[i].a >> E[i].b >> E[i].w;
sort(E + 1, E + 1 + m);
cin >> q;
for(int i = 1; i <= q; i++)
cin >> qA[i] >> qB[i];

for(int i = 1; i <= n; i++)
F[i] = i;
memset(ans, 0xff, sizeof(ans));
for(int i = 1; i <= m; i++)
{
int fa = f(E[i].a), fb = f(E[i].b);
if(fa != fb)
F[fa] = fb;
if(i % BOUND == BOUND - 1 || i == m)
{
for(int j = 1; j <= q; j++)
if(ans[j] == -1 && f(qA[j]) == f(qB[j]))
{
ans[j] = i/BOUND;
thisPeroid[i/BOUND].push_back(j);
}
}
}
memset(ans, 0xff, sizeof(ans));
for(int i = 1; i <= n; i++)
F[i] = i;
for(int i = 1; i <= m; i++)
{
int fa = f(E[i].a), fb = f(E[i].b);
if(fa != fb)
F[fa] = fb;
for(int j = 0; j < thisPeroid[i/BOUND].size(); j++)
{
int qId = thisPeroid[i/BOUND][j];
if(ans[qId] == -1 && f(qA[qId]) == f(qB[qId]))
ans[qId] = E[i].w;
}
}
for(int i = 1; i <= q; i++)
cout << ans[i] << endl;

return 0;
}

int main()
{
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cout << fixed << setprecision(16);
return MAIN();
}

表示写了树链剖分，不要骂我
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define N 100010
#define lc(x) (x<<1)
#define rc(x) ((x<<1)+1)
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
struct node{int l,r,Min;};
struct dat{int x,y,z;};
int last[N],pre[N],e[N],W[N],q[N];
int w[N],siz[N],son[N],fa[N],dep[N],top[N],b[N],ax[N],ay[N];
int Pre[N],Last[N],f[N],res[N];
int a[N];char OP[101];
int t1,t2,t3,n,len=0,size=0,Len=0,Q,m;
int exist[N];dat E[N];
void add(int x,int y,int z)
{pre[++len]=last[x];last[x]=len;e[len]=y;W[len]=z;}
void addquery(int x,int y)
{Pre[++Len]=Last[x];Last[x]=Len;q[Len]=y;}
int swap(int &x,int &y){int t=x;x=y;y=t;}
int cmp(dat a,dat b){return a.z>b.z;}
struct segtree
{
node tree[4*N];
void init(){memset(tree,0,sizeof(tree));}
void update(int x){tree[x].Min=min(tree[lc(x)].Min,tree[rc(x)].Min);}
void build(int x,int L,int R)
{
tree[x].l=L;tree[x].r=R;int mid=(L+R)>>1;
if (L==R) {tree[x].Min=a[L];return;}
build(lc(x),L,mid);build(rc(x),mid+1,R);
update(x);
}
int query(int x,int L,int R)
{
if (tree[x].l==L&&tree[x].r==R) return tree[x].Min;
int mid=(tree[x].l+tree[x].r)>>1;
if (R<=mid) return query(lc(x),L,R);
if (L>mid) return query(rc(x),L,R);
return min(query(lc(x),L,mid),query(rc(x),mid+1,R));
}
}Tree;
void DFS1(int x,int par,int Dep)
{
dep[x]=Dep;siz[x]=1;son[x]=0;
for(int p=last[x];p;p=pre[p])
{
int v=e[p];
if (par==v) continue;
fa[v]=x;b[v]=W[p];
DFS1(v,x,Dep+1);
if (son[x]==0||siz[v]>siz[son[x]]) son[x]=v;
siz[x]+=siz[v];
}
}
void DFS2(int x,int Top)
{
w[x]=++size;top[x]=Top;

a[size]=b[x];
if (son[x]!=0) DFS2(son[x],Top);
for(int p=last[x];p;p=pre[p])
{
int v=e[p];
if (v==fa[x]||v==son[x]) continue;
DFS2(v,v);
}
}
int getans(int va,int vb)
{
int f1=top[va],f2=top[vb],tmp=1e9;
while (f1!=f2)
{
if (dep[f1]<dep[f2]){swap(f1,f2);swap(va,vb);}
tmp=min(tmp,Tree.query(1,w[f1],w[va]));
va=fa[f1];f1=top[va];
}
if (va==vb) return tmp;
if (dep[va]>dep[vb]) swap(va,vb);
return min(tmp,Tree.query(1,w[son[va]],w[vb]));
}
void build_tree(int Root)
{
int i;
size=0;
DFS1(Root,-1,1);
DFS2(Root,Root);
Tree.build(1,1,size);
}
int getf(int x)
{
if (f[x]!=x) f[x]=getf(f[x]);
return f[x];
}
int main()
{
scanf("%d%d",&n,&m);int i;
FOR(i,1,n) f[i]=i;
FOR(i,1,m) scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].z);
sort(E+1,E+1+m,cmp);
FOR(i,1,m)
{
int fx=getf(E[i].x),fy=getf(E[i].y);
if (fx==fy) continue;
add(E[i].x,E[i].y,E[i].z);
add(E[i].y,E[i].x,E[i].z);
f[getf(E[i].x)]=getf(E[i].y);
}
scanf("%d",&Q);
FOR(i,1,n) exist[getf(i)]=1;
FOR(i,1,Q)
{
scanf("%d%d",&ax[i],&ay[i]);
if (getf(ax[i])!=getf(ay[i])) res[i]=-1;
else
{
int No=getf(ax[i]);
addquery(No,i);
}
}
FOR(i,1,n)
{
if (!exist[i]) continue;
build_tree(i);
for (int p=Last[i];p;p=Pre[p])
{
int v=q[p];
res[v]=getans(ax[v],ay[v]);
}
}
FOR(i,1,Q) printf("%d\n",res[i]);
}

过来抢一下沙发，这道题先跑一次MST，然后用树上倍增其他数据结构或算法求树上路径最小值
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 3048 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 3028 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 3052 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 3048 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 3036 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 3056 KiB, score = 5
测试数据 #6: Accepted, time = 62 ms, mem = 3048 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 3044 KiB, score = 5
测试数据 #8: Accepted, time = 78 ms, mem = 3052 KiB, score = 5
测试数据 #9: Accepted, time = 62 ms, mem = 3056 KiB, score = 5
测试数据 #10: Accepted, time = 78 ms, mem = 3040 KiB, score = 5
测试数据 #11: Accepted, time = 78 ms, mem = 3052 KiB, score = 5
测试数据 #12: Accepted, time = 140 ms, mem = 3760 KiB, score = 5
测试数据 #13: Accepted, time = 140 ms, mem = 3756 KiB, score = 5
测试数据 #14: Accepted, time = 124 ms, mem = 3752 KiB, score = 5
测试数据 #15: Accepted, time = 156 ms, mem = 3756 KiB, score = 5
测试数据 #16: Accepted, time = 124 ms, mem = 3752 KiB, score = 5
测试数据 #17: Accepted, time = 124 ms, mem = 3752 KiB, score = 5
测试数据 #18: Accepted, time = 140 ms, mem = 3752 KiB, score = 5
测试数据 #19: Accepted, time = 124 ms, mem = 3752 KiB, score = 5
Accepted, time = 1583 ms, mem = 3760 KiB, score = 100

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 10010
#define MAXM 50010
#define MAXQ 30010
#define MAXD 20
#define clear(x) memset(x,0,sizeof(x))
#define AddEdge(s,t,d) Add(s,t,d),Add(t,s,d)
#define inf 0x7fffffff

struct saver {
int s,t,d;
} e[MAXM];

bool cmp(saver x,saver y) {
return x.d>y.d;
}

int father[MAXN],n,m,q,Q[MAXQ][2];

int Find(int x) {
int i,j=x;
for (i=x;father[i];i=father[i]) ;
while (father[j]) {
int k=father[j];
father[j]=i;
j=k;
}
return i;
}

int up[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN];
bool f[MAXN];

struct edge {
edge *next;
int t,d;
edge () {
next=NULL;
}
} *head[MAXN];

void Add(int s,int t,int d) {
edge *p=new(edge);
p->t=t,p->d=d,p->next=head[s];
head[s]=p;
}

void BuildTree(int v) {
f[v]=false;
for (edge *p=head[v];p;p=p->next) if (f[p->t]) {
up[p->t][0]=v,Min[p->t][0]=p->d,h[p->t]=h[v]+1;
BuildTree(p->t);
}
}

int Move(int &v,int H) {
int rec=inf;
for (int i=MAXD-1;i>=0;i--) {
if (h[up[v][i]]>=H) {
rec=min(rec,Min[v][i]);
v=up[v][i];
}
}
return rec;
}

int Query(int u,int v) {
if (Find(u)!=Find(v)) return -1;
int rec=inf;
if (h[u]!=h[v]) rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]);
// printf("%d\n",rec);
if (u==v) return rec;
for (int i=MAXD-1;i>=0;i--) {
if (up[u][i]!=up[v][i]) {
rec=min(rec,min(Min[u][i],Min[v][i]));
u=up[u][i],v=up[v][i];
}
}
rec=min(rec,min(Min[u][0],Min[v][0]));
return rec;
}

int main() {
clear(father),clear(head),clear(up);
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++) scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].d);
sort(e,e+m,cmp);
for (int i=0;i<m;i++) if (Find(e[i].s)!=Find(e[i].t)) {
father[Find(e[i].s)]=Find(e[i].t);
AddEdge(e[i].s,e[i].t,e[i].d);
}
memset(f,true,sizeof(f));
for (int i=0;i++<n;) if (f[i]) h[i]=0,BuildTree(i),Min[i][0]=inf,up[i][0]=i;
for (int i=0;i++<MAXD-1;) {
for (int j=0;j++<n;) {
up[j][i]=up[up[j][i-1]][i-1];
Min[j][i]=min(Min[j][i-1],Min[up[j][i-1]][i-1]);
}
}
scanf("%d",&q);
while (q--) {
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",Query(u,v));
}
return 0;
}

不用LCA的笨人做法，先最大生成树，然后手动模拟到根的路径

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

const int maxn=10001,maxm=50001;
int n,m,egcnt,head[maxn],Q,egcnttt,belong[maxn],fa[maxn],tmp[maxn];
bool vis[maxn];
struct edge {int to,next,dis;}w[maxn<<1];
struct edge2{
    int from,to,dis;
    inline bool operator < (const edge2 x) const {return dis>x.dis;}
}edg[maxm];

inline void addedge2(int from,int to,int dis)
{
    edg[++egcnttt].to=to;
    edg[egcnttt].from=from;
    edg[egcnttt].dis=dis;
}

inline void addedge(int from,int to,int dis)
{
    w[++egcnt].to=to;
    w[egcnt].next=head[from];
    w[egcnt].dis=dis;
    head[from]=egcnt;
    w[++egcnt].to=from;
    w[egcnt].next=head[to];
    w[egcnt].dis=dis;
    head[to]=egcnt;
}

int find(int u)
{ return belong[u]==u?u:belong[u]=find(belong[u]); }

inline void kruskal()
{
    sort(edg+1,edg+egcnttt+1);
    for (register int i=1;i<=n;++i) belong[i]=i;
    for (register int i=1;i<=egcnttt&&egcnt<((n-1)<<1);++i)
    {
        int a1=find(edg[i].from);
        int a2=find(edg[i].to);
        if(a1!=a2)
        {
            belong[a1]=a2;
            addedge(edg[i].from,edg[i].to,edg[i].dis);
        }
    }
}

void dfs_fa(int u)
{
    for (register int i=head[u];i;i=w[i].next)
        if(!fa[w[i].to]) fa[w[i].to]=u,dfs_fa(w[i].to);
}

inline int solve(int x,int y)
{
    if(!fa[x]) fa[x]=-1,dfs_fa(x);
    memset(tmp,0x7f,sizeof(tmp));
    tmp[x]=10000000;
    while(x!=-1)
    {
        for (register int i=head[x];i;i=w[i].next)
        if(w[i].to==fa[x])
        {
            tmp[w[i].to]=min(w[i].dis,tmp[x]);
            break;
        }
        x=fa[x];
    }
    int ans=10000000;
    while(y!=-1)
    {
        if(tmp[y]<=10000000) {ans=min(ans,tmp[y]); break;}
        for (register int i=head[y];i;i=w[i].next)
        if(w[i].to==fa[y])
        {
            ans=min(w[i].dis,ans);
            break;
        }
        y=fa[y];
    }
    return ans;
}

int main()
{
    read(n); read(m);
    for (register int i=1,x,y,z;i<=m;++i) read(x),read(y),read(z),addedge2(x,y,z);
    kruskal();
    for (read(Q);Q;--Q)
    {
        int x,y;
        read(x); read(y);
        int a1=find(x);
        int a2=find(y);
        if(a1!=a2) {printf("-1\n"); continue;}
        printf("%d\n",solve(x,y));
    }
    return 0;
}

kruskal + 树上倍增。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int n, m;
typedef pair<int, int> pa;
vector<pa> gr[50000];
vector<pair<int, pa>> ed;
int set[50000];
int fi(int x){
    if (set[x] == x){
        return x;
    }
    return set[x] = fi(set[x]);
}
bool cmp(pair<int, pa> x, pair<int, pa> y){
    return x.first > y.first;
}
int dep[50000];
int fa[20][50000], mi[20][50000];
void mt(int x, int de){
    if (de == 1){
        fa[0][x] = x;
        mi[0][x] = 999999999;
    }
    dep[x] = de;
    For2(i, gr[x].begin(), gr[x].end()){
        if (dep[(*i).second] == 0){
            mt((*i).second, de + 1);
            fa[0][(*i).second] = x;
            mi[0][(*i).second] = (*i).first;
        }
    }
}
int main(){
    cin >> n >> m;
    For(i, 1, n){
        set[i] = i;
    }

    For(i, 1, m){
        int tkc, tkv, tjv;
        cin >> tkc >> tkv >> tjv;
        ed.emplace_back(tjv, make_pair(tkc, tkv));
    }

    sort(ed.begin(), ed.end(), cmp);
    int tms = 0, tkb = 0;

    while (tms < n - 1 && tkb < m){
        int tl = fi(ed[tkb].second.first), tr = fi(ed[tkb].second.second);
        if (tl != tr){
            set[tr] = tl;
            gr[ed[tkb].second.first].emplace_back(ed[tkb].first, ed[tkb].second.second);
            gr[ed[tkb].second.second].emplace_back(ed[tkb].first, ed[tkb].second.first);
            tms++;
        }
        tkb++;
    }
    For(i, 1, n){
        if (dep[fi(i)] == 0){
            mt(fi(i), 1);
        }
    }
    For(i, 1, 19){
        For(j, 1, n){
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
            mi[i][j] = min(mi[i - 1][j], mi[i - 1][fa[i - 1][j]]);
        }
    }




    int q;
    cin >> q;
    For(tns, 1, q){
        int x, y;
        cin >> x >> y;
        if (fi(x) != fi(y)){
            cout << -1 << endl;
            continue;
        }
        if (dep[x] < dep[y]){
            swap(x, y);
        }
        int tu = dep[x] - dep[y];
        int ans = 999999999;
        For(i, 0, 19){
            if ((tu >> i) % 2){
                ans = min(ans, mi[i][x]);
                x = fa[i][x];
            }
        }

        if (x == y){
            cout << ans << endl;
            continue;
        }
        for (int j = 19; j >= 0; --j) {
            if (fa[j][x] != fa[j][y]){
                ans = min(ans, min(mi[j][x], mi[j][y]));
                x = fa[j][x];
                y = fa[j][y];
            }
        }
        ans = min(ans, min(mi[0][x], mi[0][y]));
        cout << ans << endl;
    }
    return 0;
}

/*

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3


 *
 */

最大生成树+倍增......

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int inf=0x7f7f7f7f;
const int maxn=1e5+5;

int n,m,cnt,q;
int f[maxn],head[maxn];
struct edge{int u,v,w;}g[maxn<<1];
struct node{int u,v,next,w;}e[maxn<<1];
bool cmp(edge a,edge b){return a.w>b.w;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool vis[maxn];
int d[maxn][17],fa[maxn][17],dep[maxn];

void dfs(int u)
{
    vis[u]=1;
    for(int i=1;i<=16;i++)
    {
        if(dep[u]<(1<<i)) break;
        fa[u][i]=fa[fa[u][i-1]][i-1];
        d[u][i]=min(d[u][i-1],d[fa[u][i-1]][i-1]);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(vis[v]) continue;
        fa[v][0]=u;
        d[v][0]=e[i].w;
        dep[v]=dep[u]+1;
        dfs(v);
    }
}

int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    int tmp=dep[u]-dep[v];
    for(int i=0;i<=16;i++)
        if((1<<i)&tmp) u=fa[u][i];
    for(int i=16;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    if(u==v) return u;
    return fa[u][0];
}

int query(int u,int pre)
{
    int ans=inf;
    int tmp=dep[u]-dep[pre];
    for(int i=0;i<=16;i++)
        if(tmp&(1<<i))
            ans=min(ans,d[u][i]),
            u=fa[u][i];
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    memset(d,inf,sizeof d);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
    sort(g+1,g+m+1,cmp);
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        int u=g[i].u,v=g[i].v,w=g[i].w;
        int pu=find(u),pv=find(v);  
        if(pu==pv) continue;
        f[pu]=pv;
        tot++;
        e[++cnt]=(node){u,v,head[u],w};head[u]=cnt;
        e[++cnt]=(node){v,u,head[v],w};head[v]=cnt;
        if(tot==n-1) break;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs(i);
    scanf("%d",&q);
    while(q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(find(u)!=find(v))
        {
            printf("-1\n");
            continue;
        }
        int pre=lca(u,v);
        printf("%d\n",min(query(u,pre),query(v,pre)));
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 10005;
const int INF = 0x7fffffff;
typedef pair<int, int> pir;
#define fs first
#define se second

int n, m, f[M], fa[M][20], mins[M][20], dep[M];
vector<pir > map[M];

struct Edge{
int x, y, z;
bool operator < (const Edge& o) const{
return z > o.z;
}
}e[50005];

int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]);
}

void Kruskal(){
sort(e+1, e+1+m);
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++){
int bx = find(e[i].x);
int by = find(e[i].y);
if(bx == by) continue;
f[bx] = by;
map[e[i].x].push_back(make_pair(e[i].y, e[i].z));
map[e[i].y].push_back(make_pair(e[i].x, e[i].z));
}
}

void dfs(int x, int father, int deep){
dep[x] = deep;
for(int i = 0; i < map[x].size(); i++){
pir e = map[x][i];
if(e.fs == father) continue;
dfs(e.fs, x, deep + 1);
fa[e.fs][0] = x;
mins[e.fs][0] = e.se;
}
}

int LCA(int a, int b){
int res = INF;
if(dep[b] > dep[a]) swap(a, b);
for(int j = 14; j >= 0; j--)
if(fa[a][j] && dep[fa[a][j]] >= dep[b])
res = min(res, mins[a][j]), a = fa[a][j];
if(a == b) return res;
for(int j = 14; j >= 0; j--)
if(fa[a][j] && fa[a][j] != fa[b][j]){
res = min(res, mins[a][j]);
res = min(res, mins[b][j]);
a = fa[a][j];
b = fa[b][j];
}
res = min(res, mins[a][0]);
res = min(res, mins[b][0]);
return res;
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
Kruskal();
dfs(1, -1, 1);
for(int j = 1; j <= 14; j++)
for(int i = 1; i <= n; i++){
fa[i][j] = fa[fa[i][j-1]][j-1];
mins[i][j] = min(mins[i][j-1], mins[fa[i][j-1]][j-1]);
}
int q;
scanf("%d", &q);
for(int i = 1; i <= q; i++){
int x, y;
scanf("%d%d", &x, &y);
int bri = LCA(x, y);
if(bri == 0) printf("-1\n");
else printf("%d\n", bri);
}
return 0;
}
最大生成树 + LCA