[POJ 1935] Journey
2024-09-04 02:37:58
Link:
Solution:
一道吓唬人的水题
注意这是一棵树,两点间仅有唯一的路径!
于是每个“关键点”和起点只有一条路径,想去起点另一棵子树上的节点必须要回到起点
如果必须要回到起点,答案$res$就是除去无用边后整棵树总距离$*2$,
因为不必回到起点,最终结果为$res-mx$,$mx$为距起点的最远点的距离
除去无用边的方式:给每个“关键点”打上$vis$标记,这样最远点之后的点就不会被$dfs$到了
Code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector> using namespace std;
typedef pair<int,int> P;
#define X first
#define Y second
const int MAXN=5e4+;
vector<P> G[MAXN];
int n,k,root,dist[MAXN],vis[MAXN],mx,res,x,y,z; void dfs(int u,int anc)
{
for(int i=;i<G[u].size();i++)
{
int v=G[u][i].X;
if(v==anc) continue;
dist[v]=dist[u]+G[u][i].Y;
dfs(v,u);
if(vis[v]) vis[u]=true,res+=G[u][i].Y*; //传递标记
}
} int main()
{
scanf("%d%d",&n,&root);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(P(y,z));G[y].push_back(P(x,z));
}
scanf("%d",&k);
for(int i=;i<=k;i++)
scanf("%d",&x),vis[x]=true; //打上标记
dfs(root,);
for(int i=;i<=n;i++)
if(vis[i]) mx=max(mx,dist[i]);
printf("%d",res-mx);
return ;
}
Review:
(1)对“树”这个条件中“两点之间只有一条路径”这个性质不够敏感,
因此未能看出到达一棵子树的最远点后必须要回到起点再出发这一推论
(2)除去无用边的方法很妙:设置$vis=true$,将更远的点截去
同时传递$vis$的值来更新答案
最新文章
- php获取用户 地区 、ip地址
- SQL性能优化案例分析
- 工作上遇到的问题 DEBUG 001
- View通用
- MySQL命令行导出数据库
- ArcGIS for Sever 10.1 服务迁移与恢复
- RabbitMQ介绍4 - 编程(C#客户端示例)
- Delphi 的运算符列表
- js密码的校验(判断字符类型、统计字符类型个数)
- 帝国cms灵动标签调用tags
- Visual studio 能否定位打开文件在项目中的位置
- JS读写浏览器cookie及读取页面参数
- Linux之安全应用
- java设计模式--简单工厂
- vue 配合vue-resource调用接口,获取数据
- matplot画图kill问题,形成思路
- ORM 框架简介
- Netty 零拷贝(一)NIO 对零拷贝的支持
- 递归计算一个目录的大小【os.wallk()】
- HDU 1754 I Hate It (线段树)