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

0924

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 }
View Code

 

http://www.hskmm.com/?act=detail&tid=16191

相关文章:

  • java_string比较中的细节
  • 扫描线学习笔记
  • go-reids
  • AI完美声音克隆及情绪控制,与真人无异,Lark下载介绍
  • WSL,适用于 Linux 的 Windows 子系统
  • 9-24
  • 代码随想录算法训练营第八天 |344.反转字符串、541. 反转字符串II、LCR 122. 路径加密
  • 9/24
  • 安装与卸载JDK8
  • mysql慢sql配置
  • Linux zdb -C (zfs Debugger调试器)
  • 从零开始实现简易版Netty(八) MyNetty 实现Small规格的池化内存分配
  • 测试脚本
  • 自动化测试脚本
  • 解题报告-字符串(str.*)
  • Linux 系统中的 /dev/disk/by-id/目录作用详解
  • glTF/glb:您需要知道的一切,怎么免费获取下载
  • keepalived服务器
  • P8818 [CSP-S 2022] 策略游戏
  • FortiGate连接中国联通SDWAN
  • 第五章 运算符、表达式和语句
  • 学习问题日记-2
  • 封神台复现
  • 李之一的Java第一作
  • 2025.9.24 闲话:Lucas 定理究极证明
  • Are English people good or bad
  • 9
  • Lampiao靶场渗透wp-脏牛提权
  • 画矩形
  • NOIP 模拟赛八