【BZOJ 2753 滑雪与时间胶囊】
2024-09-28 03:45:14
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 2843 Solved: 993
[Submit][Status][Discuss]
Description
a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1<=i<=N)和一高度Hi。a180285能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。 与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是a180285 滑行的距离)。请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。 现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间
胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?
Input
输入的第一行是两个整数N,M。
接下来1行有N个整数Hi,分别表示每个景点的高度。
接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,Ui,Vi,Ki。表示
编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。
Output
输出一行,表示a180285最多能到达多少个景点,以及此时最短的滑行距离总和。
Sample Input
3 3
3 2 1
1 2 1
2 3 1
1 3 10
Sample Output
3 2
HINT
【数据范围】
对于30%的数据,保证 1<=N<=2000
对于100%的数据,保证 1<=N<=100000
对于所有的数据,保证 1<=M<=1000000,1<=Hi<=1000000000,1<=Ki<=1000000000。
Source
【题解】
①第一问可以直接bfs解决;
②可以想到如果只考虑可以到的点就和最小生成树类似,但是是有向的,直接kruskal或prim会错
(因为MST只在无向图上成立);改进一下:
③由于有高度,考虑分层即可(跑最小生成树是把高度作为第一关键字,长度作为第二关键字),优先高的,就可以处理有向的问题。
/*3 3
3 2 1
1 2 1
2 3 1
1 3 10
这个故事告诉我们证明是很重要的;
看来我要好好学数学,端正态度;
MST成立的条件是环
记得清华来的第二个学长说过:
“如果你不清楚是不是对的,就尝试去证明,到哪里证不出来了就是问题。”
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <ctime>
#include <cmath>
#define inf 0x3f3f3f3f
#define ll long long
#define N 100010
#define M 1000100
#define mem(f,a) memset(f,a,sizeof(f))
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define Eun(i,u,E,head) for(int i=head[u],v=E[i].v;i!=-1;i=E[i].next,v=E[i].v)
using namespace std;
int n,m;
int H[N],vis[N],head[N],k,fa[N],dis[N];
struct Edge{
int u,v,w,next;
bool operator <(const Edge a)const{
return (H[a.v]==H[v])? a.w>w : H[a.v]<H[v];
}
}E[*M];
queue<int>Q;
ll cnt,ans;
void adde(int u,int v,int w)
{ E[k]=(Edge){u,v,w,head[u]};
head[u]=k++;
}
void Bfs()
{ Q.push(); vis[]=; cnt=;
while (!Q.empty()){
int u=Q.front(); Q.pop();
Eun(i,u,E,head)
if (!vis[v]) cnt++,vis[v]=,Q.push(v);
}
}
int find(int x)
{ if (fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
void Kruskal()
{ sort(E,E+k);
Run(i,,n) fa[i]=i;
Run(i,,k-){
if (!vis[E[i].u]||!vis[E[i].v]) continue;
int fx=find(E[i].u),fy=find(E[i].v);
if (fx!=fy) ans+=E[i].w,fa[fx]=fy;
}
}
int main()
{ //freopen("ski.in","r",stdin);
//freopen("ski.out","w",stdout);
scanf("%d%d",&n,&m);
Run(i,,n){
scanf("%d",&H[i]);
}
int u,v,w; mem(head,-);
Run(i,,m){
scanf("%d%d%d",&u,&v,&w);
if (H[u]>=H[v]) adde(u,v,w);
if (H[u]<=H[v]) adde(v,u,w);
}
Bfs();
Kruskal();
printf("%lld %lld",cnt,ans);
return ;
}//by tkys_Austin;
最新文章
- MSSQLSERVER执行计划详解
- GTest Google的一种白盒单元测试框架 开源项目
- C# 在執行程式目錄下產生文件夾
- 【转载】Linux 信号列表
- require.js笔记
- 7-14 EXISTS子查询
- VS代码片段(snippet)创作工具——Snippet Editor(转)
- 20条IPTables防火墙规则用法!
- spring boot 数据库连接池配置
- ansible不配ssh连接,用户密码登录
- Python之向日志输出中添加上下文信息
- js动态增加秒数(自动,手动)
- iOS蓝牙BLE开发
- 【Hadoop】HDFS的java客户端编写
- webpack 4 + mockjs
- windows 8.1 启用hyper-v导致vmware 无法使用的问题解决方案(兼顾WP8.1模拟器和vmware)
- Android开发者的Anko使用指南(二)之Dialogs
- 温馨小程序前端布局Flex
- Android lrucache 实现与使用(Android内存优化)
- 一个牛公司的关于oracle数据的面试题