HDU 3440House Man(差分约束)-白红宇的个人博客

HDU 3440House Man(差分约束)

发布日期：2021-06-30 10:24:41 浏览次数：2 分类：技术文章

本文共 1433 字，大约阅读时间需要 4 分钟。

题意：

要从高度最低的地方跳到高度最高的地方每次跳跃的距离小于等于d

每次只能跳到下一个比他高但是和他高度最接近的位置

每个位置都有一个高度值并且顺序不能换最低和最高的最远距离。

定义 $s [i]$ 为点 $i$ 在的位置,这保证了相对位置

可以得到 $s [i] > s [i - 1]$

然后对于高度差相邻的两个序号 $u, v$ 为了保证能跳过去

得到 $s [u] - s [v] < = d$

而且这里一定需要 $u > v$ ,因为 $u$ 在序号上大,所以要远一些的

而且最后是从最矮的位置跑最短路还是从最高的位置,也需要用序号大小来判断

#include 
   
    using namespace std;const int maxn = 2e5+10;const int inf = 1e9;struct edge{
   	int to,nxt,w;}d[maxn]; int head[maxn],cnt=1;struct point{
   	int id,h;	bool operator < (const point&tmp )	const{
   		return h

q; q.push( s ); dis[s] = 0; while( !q.empty() ) {

int u = q.front(); q.pop(); vis[u] = 0; for(int i=head[u];i;i=d[i].nxt ) {

int v = d[i].to; if( dis[v]>dis[u]+d[i].w ) {

dis[v] = dis[u]+d[i].w; if( !vis[v] ) {

q.push( v ),vis[v] = 1; if( ++num[v]==n ) return false; } } } } return 1;}int main(){

int t,casenum = 0; cin >> t; while( t-- ) {

cin >> n >> m; for(int i=1;i<=n;i++) {

cin >> a[i].h, a[i].id = i; if( i>=2 ) add( i,i-1,-1 ); } sort( a+1,a+1+n ); for(int i=2;i<=n;i++) {

int u = a[i-1].id, v = a[i].id; if( u>v ) swap(u,v); add( u,v,m ); } int u = a[1].id, v = a[n].id; if( u>v ) swap(u,v); cout << "Case " << ++casenum << ": "; if( spfa(u) ) cout << dis[v] << endl; else cout << "-1\n"; cnt = 1; for(int i=1;i<=n;i++) head[i] = 0; }}

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109964132 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：HDU 3592 World Exhibition(--差分约束--)

下一篇：度数K限制的最小生成树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章