题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
struct edge{
int u,v,w;
bool operator<(const edge&p)const{
return w>p.w;
};
}e[N];
vector<PII> g[N];
int p[N];
int find(int x){
if(p[x]!=x){
p[x]=find(p[x]);
}
return p[x];
}
void krusal(){
sort(e+1,e+1+m);
for(int i=1;i<=m;i++)
{
auto [u,v,w]=e[i];
u=find(u),v=find(v);
if(u!=v){
p[u]=v;
g[e[i].u].emplace_back(e[i].v,e[i].w);
g[e[i].v].emplace_back(e[i].u,e[i].w);
///cout<<e[i].u<<" "<<e[i].v<<"\n";
}
}
}
int fa[N][25],w[N][25];
bool st[N];
int depth[N];
void dfs(int u,int f){
st[u]=true;
for(auto [v,ww]:g[u]){
if(v==f) continue;
depth[v]=depth[u]+1;
w[v][0]=ww;
fa[v][0]=u;
dfs(v,u);
}
}
int lca(int u,int v){
if(find(u)!=find(v)) return -1;
if(depth[u]<depth[v]) swap(u,v);
int t=depth[u]-depth[v];
int mn=inf;
for(int j=0;j<20;j++)
{
if(t>>j&1)
{
mn=min(mn,w[u][j]);
u=fa[u][j];
}
}
for(int j=19;j>=0;j--){
if(fa[u][j]!=fa[v][j])
{
mn=min({mn,w[u][j],w[v][j]});
u=fa[u][j];
v=fa[v][j];
}
}
return u==v?mn:min({mn,w[u][0],w[v][0]});
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
memset(w,0x3f,sizeof(w));
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[i]={u,v,w};
}
krusal();
for(int i=1;i<=n;i++)
{
if(!st[i])
{
depth[i]=1;
fa[i][0]=i;
dfs(i,-1);
}
}
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
w[i][j]=min(w[i][j-1],w[fa[i][j-1]][j-1]);
}
}
int q;
cin>>q;
while(q--){
int x,y;cin>>x>>y;
cout<<lca(x,y)<<"\n";
}
}
//1 2 3 4
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
//cin>>t;
while(t--) solve();
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla