UVA - 11354Bond最小生成树,LCA寻找近期公共祖先
生成 最小 寻找 公共 UVa 近期 LCA 祖先
2023-09-11 14:20:43 时间
看懂题目意思。他的意思是求将全部的城市走一遍,危急度最小。而且给
你两个s,t后让你求在走的时候,从s到t过程中危急度最大的值,并输出它,
然后就是怎样攻克了,这个题目能够说简单,也能够说难
通过思考能够知道s到t的路径进行遍历就是所谓的答案了
所以通过LCA算法就能够解决这个问题,大家能够去看看LCA在图论上的算法
/* Author: 2486 Memory: 0 KB Time: 2222 MS Language: C++11 4.8.2 Result: Accepted VJ RunId: 4236841 Real RunId: 15859210 */ #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; const int maxn=50000+5; const int maxm=100000+5; int N,M,m; int par[maxn],dist[maxn],depth[maxn],vis[maxn]; struct edge { int u,v,cost; bool operator<(const edge &a)const { return cost<a.cost; } } es[maxm]; struct ed { int to,cost; ed(int to,int cost):to(to),cost(cost) {} }; vector<ed>G[maxn]; void init(int c) { for(int i=0; i<maxn; i++) { par[i]=i; dist[i]=-1; if(c)G[i].clear(); } memset(vis,false,sizeof(vis)); } int find(int x) { return par[x]==x?x:par[x]=find(par[x]); } bool same(int x,int y) { return find(x)==find(y); } void unite(int x,int y) { x=find(x); y=find(y); par[x]=y; } int lca(int a, int b) { //a的深度<=b的深度 int m1 = -1; while(depth[a] < depth[b]) { //将深度调到一样 m1 = max(m1, dist[b]); b = par[b]; } while(a != b) {//同一时候从节点走到祖先节点 m1 = max(m1, dist[a]); m1 = max(m1, dist[b]); a = par[a], b = par[b]; } return m1; } void kj() { sort(es,es+M); init(1); int cnt=0; /**********将组成最小生成树的边全都保存起来*************/ /**********大家都懂。这是Kruskal算法*************/ for(int i=0; i<M; i++) { edge e=es[i]; if(!same(e.v,e.u)) { unite(e.v,e.u); G[e.v].push_back(ed(e.u,e.cost)); G[e.u].push_back(ed(e.v,e.cost)); } } /***********************/ dist[1]=0; depth[1]=0; queue<int>F; F.push(1); vis[1]=true; init(0); /*********这个是非常重要的**************/ /*********以1号城市为根节点,然后就是開始遍历形成一棵树**************/ /***********大家能够想象一下,假设城市在一棵树的某个节点上************/ /***********那么什么才是从一个点到还有一个点的路径呢?************/ /***********非常easy。将他们从他们自己的节点向上递推到两个点的共同祖先就能够了************/ /***********中间经历的就是从一个点到还有一个点的路径************/ /***********如此,就直接用队列处理一下就可以************/ while(!F.empty()) { int v=F.front(); F.pop(); for(int i=0; i<G[v].size(); i++) { ed e=G[v][i]; if(vis[e.to])continue; vis[e.to]=true; par[e.to]=v;//他的父亲节点 depth[e.to]=depth[v]+1;//他的深度 dist[e.to]=e.cost;//从该节点到父亲节点的危急度 F.push(e.to); } } /***********************/ } int main() { int cases=1; //freopen("D://imput.txt","r",stdin); while(~scanf("%d%d",&N,&M)) { for(int i=0; i<M; i++) { scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost); } if(cases!=1)printf("\n");//注意题目格式,须要换行 kj(); int s,t; scanf("%d",&m); while(m--) { scanf("%d%d",&s,&t);//读取命令 if(depth[s]>depth[t])swap(s,t); printf("%d\n",lca(s,t)); } cases++; } return 0; }
相关文章
- nyoj 925 国王的烦恼(最小生成树)
- Java实现 蓝桥杯 算法提高最小方差生成树
- centos8(linux): nohup生成的日志切分
- [usaco]Agri-Net(使用最小生成树算法)
- .jar包文件的生成与运行
- 基于CDS view生成的OData服务的metadata是如何加载的
- CV之IG:图像生成(Image Generation)的简介、使用方法、案例应用之详细攻略
- jittor和pytorch生成网络对比之bicyclegan
- GVRP不适用于MSTP多生成树实例的原因
- 图的最小生成树-Kruskal算法
- Leetcode 1374. 生成每种字符都是奇数个的字符串
- 【Groovy】xml 序列化 ( 使用 MarkupBuilder 生成 xml 数据 | 标签闭包下创建子标签 | 使用 MarkupBuilderHelper 添加 xml 注释 )
- PHP代码为什么不能直接保存HTML文件——>PHP生成静态页面教程
- ACM-最小生成树之畅通project——hdu1863
- 图论---最小生成树----普利姆(Prim)算法
- 使用python调用zxing库生成二维码图片
- 一个 KiCad 工程项目可以生成哪些数据?(2020-04-05)[88.69%]
- 数据结构图之二(最小生成树--克鲁斯卡尔算法)
- EOS的共识机制与区块生成
- 一文总结图像生成必备经典模型(一)
- 记录一次存储过程和pivot(行转列)函数成功生成报表的经历