HDU - 4514 湫湫系列故事——设计风景线(并查集判环)
2024-08-23 07:41:29
题目:
随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没有条件建成环形,那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设,在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线?如果不能,风景线最长能够达到多少?
其中,可以兴建的路线均是双向的,他们之间的长度均大于0。
思路:
将给出的边的两个端点用并查集放在一起,如果这两个点的祖先相等说明构成了一个环。
在这个用并查集连成的连通分量里边,找到他的root(fa[i] = i),然后先用一个BFS找到他的端点,然后从这个端点开始找树上的最长距离。
代码:
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 1000000000
#define inf 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin) using namespace std;
typedef unsigned long long ll;
const int maxn = ;
int n,m;
struct Edge
{
int to,w;
};
vector<Edge> mp[maxn];
int fa[maxn],vis[maxn],d[maxn]; int _find(int x)
{
return fa[x] == x ? x : fa[x] = _find(fa[x]);
} bool judgeLoop(int u,int v)
{
int x = _find(u);
int y = _find(v);
if(x!=y)
{
fa[x] = y;
return false;
}
return true;//x==y说明两者已经在一个连通分量里边了,也就是有环了
} int BFS(int s)//两个作用1.查找最远的结点2.计算最长的距离
{
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
vis[s] = ;
queue<int> que;
que.push(s);
int ed = s,mmax=;
while(!que.empty())
{
int u = que.front();
que.pop();
for(int i=; i<mp[u].size(); i++)
{
Edge e = mp[u][i];
if(vis[e.to] == )
{
d[e.to] = d[u]+e.w;//获取从根节点到e.to结点的距离
vis[e.to] = ;
que.push(e.to);
if(d[e.to]>mmax)//找到这棵树的距离根节点最远的结点
{
ed = e.to;
mmax = d[e.to];
}
}
}
}
return ed;
} int main()
{
//FRE();
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=; i<maxn; i++) { fa[i] = i; mp[i].clear();}
bool ok = false;
for(int i=; i<m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
mp[u].push_back(Edge{v,w});
mp[v].push_back(Edge{u,w});
if(judgeLoop(u,v)) { ok = true; }
}
if(ok)
{
printf("YES\n");
continue;
}
int ans = ;
for(int i=; i<=n; i++)
{
if(fa[i]==i)//找到这个树的根节点(人为设置的)
{
int root = BFS(i);
int temp = BFS(root);
ans = max(ans,d[temp]);
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- android 自定义控件——(三)水平线、虚线
- 如何查看前端部署的tracker代码
- 【C语言】结构体
- 用ajax和js怎么做出滚动条滚到最下面分页
- 用Jenkins配置自动化构建
- 11g RAC r2 的启停命令概述1
- haporoxy的keeplaive ZZ
- (原创)优酷androidclient 下载中 bug 解决
- vue 路由懒加载 使用,优化对比
- 2018-2019-20175334实验一《Java开发环境的熟悉》实验报告
- qnx i2c 学习 二
- IVIEW TREE问题总结
- yum 安装时错误 Errno 14 Couldn&#39;t resolve host 解决办法
- 关于vue项目中,手动定义的scrollTop的值
- 使用Sublime Text 2 和 MinGW 搭建C开发环境
- ecshop2.73修改密码方法|ecshop2.73修改密码方法
- [mysqli_escape]mysql转义两次
- Python中的base64模块
- Codeforces 859E Desk Disorder 并查集找环,乘法原理
- 1 Scala基本概念 +IDE
热门文章
- hdu4608 I-number
- PCB AdminMongo安装使用
- E20180128-hm
- bzoj 3894 文理分科【最小割+dinic】
- 洛谷P3211 [HNOI2011]XOR和路径(期望dp+高斯消元)
- thinkphp5.0常遇到的错误
- DecimalFormat数字格式化用法“0”和“#”的区别
- Hdu 5384 Danganronpa (AC自动机模板)
- poj 3253 Fence Repair (水哈夫曼树)
- Linux环境下Apache反向代理金蝶中间件Apusic集群