BZOJ3732 Network

news/2023/12/10 15:48:10

这貌似是13年的noip最后一道吧?、、、

蒟蒻只会这种题呢、、、

Kruskal求出MST,然后倍增就好了

 

  1 /**************************************************************
  2     Problem: 3732
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:268 ms
  7     Memory:4412 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12  
 13 using namespace std;
 14 const int N = 16005;
 15 const int M = 30005;
 16  
 17 struct Edge {
 18     int x, y, v;
 19      
 20     inline bool operator < (const Edge &x) const {
 21         return v < x.v;
 22     }
 23 } E[M];
 24  
 25 struct edge {
 26     int next, to, v;
 27     edge() {}
 28     edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}
 29 } e[M];
 30  
 31 struct tree_node {
 32     int fa[16], mx[16], dep;
 33 } tr[N];
 34  
 35 int n, m;
 36 int fa[N];
 37 int tot, first[N];
 38  
 39 inline int read() {
 40     int x = 0;
 41     char ch = getchar();
 42     while (ch < '0' || '9' < ch)
 43         ch = getchar();
 44     while ('0' <= ch && ch <= '9') {
 45         x = x * 10 + ch - '0';
 46         ch = getchar();
 47     }
 48     return x;
 49 }
 50  
 51 inline void Add_Edges(int x, int y, int v) {
 52     e[++tot] = edge(first[x], y, v), first[x] = tot;
 53     e[++tot] = edge(first[y], x, v), first[y] = tot;
 54 }
 55  
 56 int find_fa(int x) {
 57     return x == fa[x] ? x : fa[x] = find_fa(fa[x]);
 58 }
 59  
 60 void Kruskal() {
 61     int i, cnt, fa1, fa2;
 62     sort(E + 1, E + m + 1);
 63     for (i = 1; i <= n; ++i)
 64         fa[i] = i;
 65     for (i = 1, cnt = 0; i <= m; ++i) {
 66         fa1 = find_fa(E[i].x), fa2 = find_fa(E[i].y);
 67         if (fa1 != fa2) {
 68             fa[fa1] = fa2, ++cnt;
 69             Add_Edges(E[i].x, E[i].y, E[i].v);
 70             if (cnt == n - 1) break;
 71         }
 72     }
 73 }
 74  
 75 void dfs(int p) {
 76     int x, y;
 77     for (x = 1; x < 16; ++x) {
 78         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1];
 79         tr[p].mx[x] = max(tr[p].mx[x - 1], tr[tr[p].fa[x - 1]].mx[x - 1]);
 80     }
 81     for (x = first[p]; x; x = e[x].next)
 82         if ((y = e[x].to) != tr[p].fa[0]) {
 83             tr[y].dep = tr[p].dep + 1;
 84             tr[y].fa[0] = p, tr[y].mx[0] = e[x].v;
 85             dfs(y);
 86         }
 87 }
 88  
 89 int query(int x, int y) {
 90     int res = 0, i;
 91     if (tr[x].dep < tr[y].dep) swap(x, y);
 92     for (i = 15; ~i; --i)
 93         if (tr[tr[x].fa[i]].dep >= tr[y].dep) {
 94             res = max(res, tr[x].mx[i]);
 95             x = tr[x].fa[i];
 96         }
 97     for (i = 15; ~i; --i)
 98         if (tr[x].fa[i] != tr[y].fa[i]) {
 99             res = max(res, max(tr[x].mx[i], tr[y].mx[i]));
100             x = tr[x].fa[i], y = tr[y].fa[i];
101         }
102     if (x != y)
103         res = max(res, max(tr[x].mx[0], tr[y].mx[0]));
104     return res;
105 }
106  
107 int main() {
108     n = read(), m = read();
109     int Q = read(), i, x, y;
110     for (i = 1; i <= m; ++i)
111         E[i].x = read(), E[i].y = read(), E[i].v = read();
112     Kruskal();
113     tr[1].dep = 1;
114     dfs(1);
115     while (Q--) {
116         x = read(), y = read();
117         printf("%d\n", query(x, y));
118     }
119     return 0;
120 }
View Code

 

转载于:https://www.cnblogs.com/rausen/p/4160979.html


https://dhexx.cn/news/show-16979.html

相关文章

Kali Linux Web 渗透测试视频教程— 第十六课-拒绝服务攻击

Kali Linux Web 渗透测试视频教程—第十六课-拒绝服务攻击 文/玄魂 目录 Kali Linux Web 渗透测试视频教程— 第十六课-拒绝服务攻击...................... 1 DoS.........................................................................................................…

java开发_2020年Java开发就业前景怎么样?

点击上方“千锋教育”后台回复「 JAVA」&#xff0c;领取视频学习教程Java属于编程语言的核心语言&#xff0c;很多公司都在用Java&#xff0c;Java语言开发优势显著稳定性好&#xff0c;在服务器端Java发挥高性能、安全稳健的特性。2019年Java岗位需求仍呈现持续上升趋势供不应…

git学习 本地常用操作01

注意&#xff1a; Microsoft的Word格式是二进制格式&#xff0c;因此&#xff0c;版本控制系统是没法跟踪Word文件的改动不要使用Windows自带的记事本编辑任何文本文件开始git项目&#xff1a; 初始化本地项目&#xff1a; 初始化&#xff1a;git init; //git init dir 同时创建…

Havel-Hakimi定理(握手定理)

Havel-Hakimi定理&#xff08;握手定理&#xff09; 由非负整数组成的非增序列s&#xff08;度序列&#xff09;&#xff1a;d1&#xff0c;d2&#xff0c;…&#xff0c;dn&#xff08;n>2&#xff0c;d1>1&#xff09;是可图的&#xff0c;当且仅当序列&#xff1a; s1…

vscode在html看到图片的插件_三个强大的PPT插件工具

今天分享三个强大的PPT插件工具&#xff0c;我知道&#xff0c;很多同学都不需要做很专业的PPT&#xff0c;只要不是太丑&#xff0c;看得过去&#xff0c;直接套用模板就可以了。即使我们自己会做专业的PPT&#xff0c;但是也会偷懒&#xff0c;直接套用模板&#xff0c;差一点…

IOS开发网络篇—数据安全

一、简单说明 1.说明 在开发应用的时候&#xff0c;数据的安全性至关重要&#xff0c;而仅仅用POST请求提交用户的隐私数据&#xff0c;还是不能完全解决安全问题。 如&#xff1a;可以利用软件&#xff08;比如Charles&#xff09;设置代理服务器&#xff0c;拦截查看手机的请…

javaweb 图书管理系统完整代码_基于Java web的图书管理系统

源码编号&#xff1a;B-E00029点击查看(分类规则)项目类型&#xff1a;Java EE项目(非开源)项目名称&#xff1a;基于Java web的图书管理系统(library_system)当前版本&#xff1a;V2.0.2版本难度等级&#xff1a;✩✩复杂程度&#xff1a;✩✩ 点击查看难度等级用户类型&#…

python学习笔记24(路径与文件 (os.path包, glob包))

python学习笔记24&#xff08;路径与文件 (os.path包, glob包)&#xff09; os.path模块主要用于文件的属性获取&#xff0c;在编程中经常用到&#xff0c;以下是该模块的几种常用方法。 >>> import os.path >>> path /home/ethon/doc/file.txt >>>…

代码和普通的java_【Java基础】2、Java中普通代码块,构造代码块,静态代码块区别及代码示例...

Java中普通代码块&#xff0c;构造代码块&#xff0c;静态代码块区别及代码示例。Java中普通代码块&#xff0c;构造代码块&#xff0c;静态代码块区别及代码示例执行顺序&#xff1a;静态代码块>静态方法(main方法)>构造代码块>构造方法。其中静态代码块在jvm加载类的…

imp 日志_海贼王:罗杰航海日志公开,把2个 “冥王”留给了路飞

本平台为了热爱漫画&#xff0c;热爱壁纸美图和热爱二次元的朋友们而建&#xff0c; 仅作兴趣分享。如有侵权请联系删除。声明&#xff1a;本公众号所有图片均来源于网络&#xff0c;如有侵权或违法行为&#xff0c;请及时告知删除。本公众号所有资源仅用于漫迷学习交流&#x…