POJ 3169 Layout(差分约束线性差分约束)-白红宇

POJ 3169 Layout(差分约束线性差分约束)

阅读量：4544 次

发布时间：2019-06-08

本文共 1841 字，大约阅读时间需要 6 分钟。

题意：

有N头牛，有以下关系：

（1）A牛与B牛相距不能大于k

（2）A牛与B牛相距不能小于k

（3）第i+1头牛必须在第i头牛前面

给出若干对关系（1），（2）

求出第N头牛与第一头牛的最长可能距离，若无解输出-1，若无限长输出-2

分析：

3个关系对应的 <= 式子是：

dis[b] - dis[a] <= d(1)

dis[a] - dis[b] <= -d(2)

dis[i] - dis[i+1] <= -1(2)

目标式：dis[N] - dis[1] <= T

要求这个T就是建好图后跑源点为1的最短路，有负权环路则无解输出-1，不连通则输出-2(无约束关系)。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define rep(i,a,b) for(int i = a; i < b;i++)#define _rep(i,a,b) for(int i = a; i <= b;i++)using namespace std;const int inf = 1e9 + 7;const int maxn = 1000 + 7;int n , m;struct edge{ int to , d; edge(int _to, int _d): to(_to), d(_d){}};vector
                 
                   G[maxn];void add_edge(int u, int v, int d){ G[u].push_back(edge(v,d));}int N , ML, MD;int dis[maxn], enter_cnt[maxn];int spfa(){ fill(dis, dis+maxn, inf); memset(enter_cnt, 0, sizeof(enter_cnt)); bool vis[maxn]; memset(vis, 0, sizeof(vis)); queue
                  
                    q; vis[1] = 1; dis[1] = 0; q.push(1); ++enter_cnt[1]; while(!q.empty()){ int u = q.front(); rep(i,0,G[u].size()){ int v = G[u][i].to, d = G[u][i].d; if(dis[v] > dis[u] + d){ dis[v] = dis[u] + d; if(!vis[v]){ if(++enter_cnt[v] >= N) return -1;//入队次数大于等于N代表存在负权环路 vis[v] = 1; q.push(v); } } } vis[u] = 0; q.pop(); } return dis[N]; }int main(){ cin >> N >> ML >> MD; rep(i,0,ML){ int a, b, d; cin >> a >> b >> d; //dis[b] - dis[a] <= d add_edge(a,b,d); } rep(i,0,MD){ int a, b, d; cin >> a >> b >> d; // dis[b] - dis[a] >= d -> dis[a] - dis[b] <= -d add_edge(b,a,-d); } rep(i,1,N){ //dis[i+1] - dis[i] >= 1 -> dis[i] - dis[i+1] <= -1 add_edge(i+1,i,-1); } int ans = spfa(); if(ans == -1){ printf("-1\n"); }else if(ans == inf){ printf("-2\n"); }else printf("%d\n", ans); return 0;}