当前位置：首页 > news >正文

0924

news 2026/6/11 4:57:07

https://www.luogu.com.cn/problem/P1967

换了一种做法做出来了

不记得老师之前怎么讲的

  1 #include<bits/stdc++.h>
  2 #define R 200001
  3 using namespace std;
  4 int n,m,cnt,q;
  5 struct node
  6 {
  7     int u,v,dis;
  8 }edge[R];
  9 bool cmp(node a,node b)
 10 {
 11     return a.dis>b.dis;
 12 }
 13 struct node2
 14 {
 15     int v,nxt;
 16 }E[R];
 17 int head[R],tmp;
 18 int val[R],ff[R],vis[R];
 19 int fa[R],top[R],son[R];
 20 int size[R],dep[R];
 21 void add(int u,int v)
 22 {
 23     E[++tmp].nxt=head[u];
 24     E[tmp].v=v;
 25     head[u]=tmp;
 26 }
 27 int find(int x)
 28 {
 29     if(x==ff[x]) return x;
 30     else return ff[x]=find(ff[x]);
 31 }
 32 void dfs1(int u,int pa)
 33 {
 34     size[u]=1;
 35     vis[u]=1;
 36     for(int i=head[u];i;i=E[i].nxt)
 37     {
 38         int v=E[i].v;
 39         if(v==pa) continue;
 40         dep[v]=dep[u]+1;
 41         fa[v]=u;
 42         dfs1(v,u);
 43         size[u]+=size[v];
 44         if(size[v]>size[son[u]]) son[u]=v;
 45     }
 46 }
 47 void dfs2(int u,int tp)
 48 {
 49     top[u]=tp;
 50     if(son[u]) dfs2(son[u],tp);
 51     for(int i=head[u];i;i=E[i].nxt)
 52     {
 53         int v=E[i].v;
 54         if(v==fa[u]||v==son[u]) continue;
 55         dfs2(v,v);
 56     }
 57 }
 58 void kruskal()
 59 {
 60     sort(edge+1,edge+1+m,cmp);
 61     for(int i=1;i<=n;i++) ff[i]=i;
 62     for(int i=1;i<=m;i++)
 63     {
 64         int fu=find(edge[i].u),fv=find(edge[i].v);
 65         if(fu!=fv)
 66         {
 67             val[++cnt]=edge[i].dis;
 68             ff[cnt]=ff[fu]=ff[fv]=cnt;
 69             add(fu,cnt),add(cnt,fu),add(fv,cnt),add(cnt,fv);
 70         }
 71     }
 72     for(int i=1;i<=cnt;i++)
 73     {
 74         if(!vis[i])
 75         {
 76             int f=find(i);
 77             dfs1(f,0);
 78             dfs2(f,f);
 79         }
 80     }
 81 }
 82 int LCA(int u,int v)
 83 {
 84     while(top[u]!=top[v])
 85     {
 86         if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
 87         else v=fa[top[v]];
 88     }
 89     return dep[u]<dep[v]?u:v;
 90 }
 91 int main()
 92 {
 93     cin>>n>>m;
 94     cnt=n;
 95     for(int i=1;i<=m;i++) cin>>edge[i].u>>edge[i].v>>edge[i].dis;
 96     kruskal();
 97     cin>>q;
 98     while(q--)
 99     {
100         int u,v;
101         cin>>u>>v;
102         if(find(u)!=find(v)) puts("-1");
103         else cout<<val[LCA(u,v)]<<endl;;
104     }
105     return 0;
106 }