POJ 3169 C - Layout

题意

有n头奶牛从1到n编号，按照编号顺序站成一排，有可能有多头奶牛站在同一个坐标上。一些奶牛互相喜欢，所以他们的距离不能大于某个距离，一些奶牛互相讨厌，所以他们的距离不能小于某个距离，请计算如果可能的话1到n的最大距离是多少

分析

标准的差分约束的裸题。题中的条件可以做如下转化

1.A和B的距离不得超过x： B-A<=x

2.C和D的距离不得小于y：C-D>=y也就是D-C<=-y

3.奶牛按照编号顺序排序：位置 pos[i+1]-pos[i]>=0也就是pos[i]-pos[i+1]<=0

这样把关系全部变成了小于关系，求最大距离的话建图以后跑一个最短路就行。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <queue>

 using namespace std;

 const int maxn=+;

 const int maxm=+;

 const int INF=;

 int head[maxn],Next[maxm],to[maxm],val[maxm];

 int n,ml,md,sz;

 void add_edge(int a,int b,int w){

     ++sz;

     to[sz]=b;

     val[sz]=w;

     Next[sz]=head[a];

     head[a]=sz;

 }

 int a,b,w;

 int spfa(){

     int d[maxn],vis[maxn],cnt[maxn];

     memset(vis,,sizeof(d));

     memset(cnt,,sizeof(cnt));

     for(int i=;i<=n;i++)d[i]=INF;

     queue<int>q;

     q.push(n);

     d[n]=;vis[n]=;cnt[n]=;

     while(!q.empty()){

         int u=q.front();q.pop();vis[u]=;

     //    cout<<u<<endl;

         for(int i=head[u];i;i=Next[i]){

             int v=to[i];

             if(d[v]>d[u]+val[i]){

                 d[v]=d[u]+val[i];

                 if(!vis[v]){

                     vis[v]=;

                     q.push(v);

                     cnt[v]++;

                     if(cnt[v]>n){

                         return -;

                     }

                 }

             }

         }

     }

     if(d[]==INF)

         return -;

     return d[];

 }

 int main(){

     scanf("%d%d%d",&n,&ml,&md);

     for(int i=;i<=ml;i++){

         scanf("%d%d%d",&a,&b,&w);

         add_edge(b,a,w);

     }

     for(int i=;i<=md;i++){

         scanf("%d%d%d",&a,&b,&w);

         add_edge(a,b,-w);

     }

     for(int i=;i<n;i++){

         add_edge(i,i+,);

     }

     int ans=spfa();

     printf("%d",ans);

 return ;

 }

巴特西

POJ 3169 C - Layout

最新文章

热门文章