POJ . 3169 Layout

链接：http://poj.org/problem?id=3169

题意 ： 

       有N头奶牛排队喂食，它们之间有相互喜欢的，所以这两头相互喜欢的奶牛之间的距离要小于等于ML，同时，有相互讨厌的的奶牛，它们之间的距离要大于等于MD，而且奶牛的位置和他们的标号顺序相同，求奶牛1到奶牛N的最大距离，如果没有最大距离输出-1，最大距离无限大则-2；

       这道题的思路是利用差分约束系统来建图 ：

       如果u，v的最大距离为val ：( 1 )  dis[ v ] - dis[ u ] < = val;

       如果u，v的最小距离为val： ( 2 )  dis[ u ] - dis[ v ] < = - val;

       又由于它们站位顺序要与编号顺序相同，所以说还需满足：( 3 ) dis[ i ] - dis[ i - 1 ] > = 0;

       由此我们就可以建图了；

代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 2 * (1e6 + 1);queue< int > q;int tov[N],next[N],head[N],w[N],cnt[1001],dis[N],tot,n,p,m;bool vis[1001];void add(int u,int v,int val){  tot++;  tov[tot] = v;  next[tot] = head[u];  w[tot] = val;  head[u] = tot;}int spfa(){  vis[1] = true;  dis[1] = 0;  q.push(1);  cnt[1]++;  while (!q.empty()){      int u = q.front();      q.pop();      for (int i = head[u];i;i = next[i]){        int v = tov[i];        if (dis[v] > dis[u] + w[i]){            dis[v] = dis[u] + w[i];            if (!vis[v]){              if ((++cnt[v]) > n) return -1;              vis[v] = true;              q.push(v);            }        }      }      vis[u] = false;  }  if (dis[n] == 1e9 + 7) return -2;  return dis[n];}int main(){  scanf("%d%d%d",&n,&p,&m);  for (int i = 1;i <= n;i++) dis[i] = 1e9 + 7,add(i,i - 1,0);  //满足不等式3  for (int i = 1;i <= p;i++){      int u,v,d;      scanf("%d%d%d",&u,&v,&d);      add(u,v,d); //满足不等式1  }  for (int i = 1;i <= m;i++){      int u,v,d;      scanf("%d%d%d",&u,&v,&d);      add(v,u,-d);  //满足不等式2  }  printf("%d",spfa());  return 0;}