hdu3440 House Man

本文主要是介绍hdu3440 House Man，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有n个房子，严格按从矮到高依次跳，跳的两个房子之间的距离要<=d，

差分约束。求最长路，按y-x<=d 建边。

需要注意的是，按高度排序后建边，需要考虑1和n的顺序问题。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll long long
const int maxn=1010;
const int maxm=1000000;
using namespace std;struct edge
{int h,id;
}p[maxn];struct node
{int v,w,next;
}e[maxm];int h,head[maxn],d[maxn],inq[maxn],outq[maxn],n,pre[maxn];bool cmp(edge a,edge b)
{return a.h<b.h;
}void init()
{memset(head,-1,sizeof head);h=0;
}void addedge(int a,int b,int c)
{e[h].v=b;e[h].w=c;e[h].next=head[a];head[a]=h++;
}int spfa(int s)
{int i,v,w,x;for(i=0;i<=n;i++)d[i]=1000000000;memset(inq,0,sizeof inq);memset(outq,0,sizeof outq);queue<int> q;q.push(s);inq[s]=1;d[s]=0;while(!q.empty()){x=q.front();q.pop();inq[x]=0;outq[x]++;if(outq[x]>n) return -1;for(i=head[x];i!=-1;i=e[i].next){v=e[i].v;w=e[i].w;if(d[v]>w+d[x]){d[v]=w+d[x];if(!inq[v]){inq[v]=1;q.push(v);}}}}return 1;
}int main()
{int icy,i,D,T=1,s,t;scanf("%d",&icy);while(icy--){init();scanf("%d%d",&n,&D);for(i=1;i<=n;i++){scanf("%d",&p[i].h);p[i].id=i;}sort(p+1,p+n+1,cmp);for(i=2;i<=n;i++){pre[p[i].id]=i;if(p[i-1].id<p[i].id) addedge(i-1,i,D);else addedge(i,i-1,D);}pre[p[1].id]=1;for(i=2;i<=n;i++)//原来相邻的房子 要用现在的编号来建边addedge(pre[i],pre[i-1],-1);if(p[1].id<p[n].id) s=1,t=n;else s=n,t=1;printf("Case %d: ",T++);if(spfa(s)==-1) printf("-1\n");else printf("%d\n",d[t]);}return 0;
}

这篇关于hdu3440 House Man的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---