首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。