1731: [Usaco2005 dec]Layout 排队布局*

1731: [Usaco2005 dec]Layout 排队布局

题意：

n头奶牛在数轴上，不同奶牛可以在同个位置处，编号小的奶牛必须在前面。m条关系，一种是两头奶牛距离必须超过d，一种是两头奶牛距离不能超过d。要求：如果不存在情况满足要求则输出-1，奶牛1到n的距离可以为无限大输出-2，否则输出1到n的最大距离。

题解：

差分约束系统。注意：如果是求最大值，则定义限制条件设定为≤并跑最短路，因为得到的是满足条件的最大值，如果是求最小值，则定义限制条件设定为≥并跑最长路，因为得到的是满足条件的最小值。因此按关系两边同时编号大的要向编号小的连边，之后求最短路：若存在负环输出-1，最短路为无限大输出-2，否则输出最短路。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #define ll long long

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 1010

 #define INF 1e16

 using namespace std;

 inline ll read(){

     char ch=getchar(); ll f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 struct e{int t; ll w; int n;}; e es[maxn*]; int g[maxn],ess;

 void pe(int f,int t,ll w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}

 int n,m1,m2,cnt[maxn]; ll d[maxn]; bool inq[maxn]; deque<int>q;

 ll spfa(){

     memset(inq,,sizeof(inq)); memset(cnt,,sizeof(cnt)); inc(i,,n)d[i]=INF;

     q.push_back(); inq[]=; d[]=; cnt[]=;

     while(!q.empty()){

         int x=q.front(); q.pop_front(); inq[x]=;

         for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){

             d[es[i].t]=d[x]+es[i].w;

             if(!inq[es[i].t]){

                 if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);

                 inq[es[i].t]=; cnt[es[i].t]++; if(cnt[es[i].t]>=n)return -;

             }

         }

     }

     if(d[n]==INF)return -; return d[n];

 }

 int main(){

     n=read(); m1=read(); m2=read();

     inc(i,,m1){int x=read(),y=read(),z=read(); if(x>y)swap(x,y); pe(x,y,z);}

     inc(i,,m2){int x=read(),y=read(),z=read(); if(x>y)swap(x,y); pe(y,x,-z);} inc(i,,n-)pe(i+,i,);

     printf("%lld",spfa()); return ;

 }

20161018