2023年7月30日发(作者：)

HDU3440（HouseMan差分约束简单题）题意： 有N个在⼀条直线上的房⼦, 每个房⼦有着不同的⾼度, ⼀个超⼈可以将这些房⼦左右移动，但不能改变房⼦之间的相对位置.现在超⼈要从最矮的房⼦跳到刚好⽐他⾼的房⼦上⾯, 且每次跳的房⼦都要⽐当前房⼦要⾼.那么最后超⼈肯定会跳到最⾼的房⼦上⾯, 现在给出超⼈能够跳的最远距离, 问: 如何摆放这些房⼦, 使得超⼈能够经过所有的房⼦跳到最⾼的房⼦, ⼜要使最矮的房⼦和最⾼的房⼦之间的距离最远??思路：1.按⾼度排完序后 ⾼度相邻的两个房⼦距离不超过D2.第i+1个房⼦距离第i个房⼦>=1再者就是注意 是⼩编号连向⼤编号。 注意求答案的时候1 n 那个是s/t.#include

#define fnq freopen("","r",stdin)using namespace std;const int N=1e4+5,INF=0x3f3f3f3f;struct Edge{int to,nex,len;}edge[N];int head[N<<1],tot;inline void add(int from,int to,int len){edge[++tot]=(Edge){to,head[from],len},head[from]=tot;}int vis[N],out[N],dis[N];queueq;int spfa(int s,int t,int n){ while(!()) (); for(int i=1;i<=n;++i) vis[i]=out[i]=0,dis[i]=INF; dis[s]=0,(s),vis[s]=1; int flag=0; while(!()){ int x=();(),vis[x]=0; if((++out[x])>n) {flag=1;break;} for(int i=head[x];i;i=edge[i].nex){ int y=edge[i].to,l=edge[i].len; if(dis[y]>dis[x]+l){ dis[y]=dis[x]+l; if(!vis[y]) {vis[y]=1,(y);}; } } } return (flag)?-1:dis[t];}struct node{int h,id;}a[N];inline int cmp(node A,node B){return A.hD) {flag=1;break;} add(u,v,D); } if(flag) {printf("Case %d: -1n",++cas);continue;} int s=min(a[1].id,a[n].id),t=a[1].id+a[n].id-s; printf("Case %d: %dn",++cas,spfa(s,t,n)); }}