POJ 3169 Layout——————简单差分约束（转化为最短路）

阳光穿透心脏的1/2处 2021-12-01 10:30 232阅读 0赞

# [Layout][] #

Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 17094 Accepted: 8231

**Description**

Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1…N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).

Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

**Input**

Line 1: Three space-separated integers: N, ML, and MD.

Lines 2…ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

Lines ML+2…ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

**Output**

Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

**Sample Input**

4 2 1  
1 3 10  
2 4 20  
2 3 3

**Sample Output**

**Hint**

Explanation of the sample:

There are 4 cows. Cows \#1 and \#3 must be no more than 10 units apart, cows \#2 and \#4 must be no more than 20 units apart, and cows \#2 and \#3 dislike each other and must be no fewer than 3 units apart.

The best layout, in terms of coordinates on a number line, is to put cow \#1 at 0, cow \#2 at 7, cow \#3 at 10, and cow \#4 at 27.

--------------------

题目描述

> 像其他人一样，奶牛在排队饲料时喜欢靠近他们的朋友。 FJ有N（2 <= N <= 1,000）个编号为1…N的奶牛从左到右按照编号从小到大站在一条直线上等待饲料。牛的数量与它们的编号相同，因为它们可能相当具有挑战性，所以有可能两头或多头奶牛可以在同一位置排队（也就是说，如果我们将每只奶牛看作是位于在数字线上的某个坐标上，那么两个或更多的母牛可以共享相同的坐标）。  
> 一些奶牛喜欢彼此，并希望彼此在一定距离内排队。有些人真的不喜欢对方，并希望至少隔开一定的距离。 ML（1 <= ML <= 10,000）约束的列表描述了哪些母牛彼此相似以及它们可以被分开的最大距离; MD约束的后续列表（1 <= MD <= 10,000）告诉哪些母牛不喜欢彼此以及它们必须被分开的最小距离。  
> 如果可能，您的工作是计算母牛1和母牛N之间满足距离约束的最大可能距离。

输入

> 第1行：三个空格分隔的整数：N，ML和MD。  
> 第2行…ML + 1：每行包含三个空格分隔的正整数：A，B和D，其中1 <= A <B <= N.奶牛A和B必须至多D（1 <= D <= 1,000,000）。  
> ML + 2…ML + MD + 1行：每行包含三个空格分隔的正整数：A，B和D，其中1 <= A <B <= N.奶牛A和B必须至少为D 1 <= D <= 1,000,000）。

输出

> 第1行：一个整数。如果不能排队，则输出-1。如果母牛1和N可以任意分开，输出-2。否则输出母牛1和N之间的最大可能距离。

记第i号牛的位置是 d \[ i \] d\[i\] d\[i\]。  
首先，牛是按照编号顺序排列的，所以有 d \[ i \] ≤ d \[ i + 1 \] d\[i\] ≤ d\[i+1\] d\[i\]≤d\[i\+1\]成立。  
其次，对于每对关系好的牛之间的最大距离限制，都有 d \[ A L \] + D L ≥ d \[ B L \] d\[AL\]+DL≥d\[BL\] d\[AL\]\+DL≥d\[BL\]成立。  
同样，对于每对关系不好的牛，都有 d \[ A D \] + D D ≤ \[ B D \] d\[AD\]+DD≤\[BD\] d\[AD\]\+DD≤\[BD\]成立。  
因此，原问题可以转化为在满足这三类不等式的情况下，求解 d d d的 d \[ N \] − d \[ 1 \] d\[N\]-d\[1\] d\[N\]−d\[1\]的最大值的问题。  
这是线性规划问题，可以使用单纯形法等较复杂的算法求解。但是这道题有更加简单的解法。

这些不等式的特点是所有的式子的两边都只出现了1个变量。实际上，图上的最短路问题也可以用这样的形式表示出来。记从起点 s s s出发，到各个顶点的最短距离为 d ( v ) d(v) d(v)。  
因此，对于每条权值为 w w w的边 e = ( v ， u ) e=(v，u) e=(v，u)，都有 d ( v ) + w > = d ( u ) d(v)+w>=d(u) d(v)\+w>=d(u)成立。  
反之，在满足全部这些约束不等式的 d d d中， d ( v ) − d ( s ) d(v)-d(s) d(v)−d(s)的大值就是从 s s s到 v v v的最短距离。需要注意这里不是最小值，而是最大值对应着最短距离。

把原来的问题和最短路问题进行比较就可以发现，两个问题都是完全一样的形式。也就是说，可以通过把原来的问题的每一个约束不等式对应成图中的一条边来构图，然后通过解决最短路问题来解决原问题。首先把顶点编号为 1 1 1~ N N N。 d \[ i \] ≤ d \[ i + 1 \] d\[i\]≤d\[i+1\] d\[i\]≤d\[i\+1\]变形为 d \[ i + 1 \] + 0 ≥ d \[ i \] d\[i+1\]+0≥d\[i\] d\[i\+1\]\+0≥d\[i\]  
因此从顶点计 i + 1 i+1 i\+1向顶点 i i i连一条权值为 0 0 0的边。同样 d \[ A L \] + D L ≥ d \[ B L \] d\[AL\]+DL≥d\[BL\] d\[AL\]\+DL≥d\[BL\]对应从顶点 A L AL AL向顶点 B L BL BL连一条权值为 D L DL DL的边， d \[ A D \] + D D ≤ d \[ B D \] d\[AD\]+DD≤d\[BD\] d\[AD\]\+DD≤d\[BD\]对应从顶点 B D BD BD向顶点 A D AD AD连一条权值为 − D D -DD −DD的边。所求的问题是 d \[ N \] − d \[ 1 \] d\[N\]-d\[1\] d\[N\]−d\[1\]的最大值，对应为顶点 1 1 1到顶点 N N N的最短距离。由于图中存在负权边，因此不使用 D i j k s t r a Dijkstra Dijkstra算法而是使用 B e l l m a n − F o r d Bellman-Ford Bellman−Ford算法求解。  
即使这样复杂度也只有 O ( N ( N + M L + M D ) ) O(N(N+ML+MD)) O(N(N\+ML\+MD))，可以在规定时间内求解。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e4+7;
    
    
    int AL[MAXN], BL[MAXN], DL[MAXN];
    int AD[MAXN], BD[MAXN], DD[MAXN];
    int d[MAXN];
    
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
    
            int N, ML, MD;
            scanf("%d %d %d",&N, &ML, &MD);
    
    
            for(int i=0;i<ML;++i)
                    scanf("%d %d %d",&AL[i],&BL[i], &DL[i]);
            for(int i=0;i<MD;++i)
                    scanf("%d %d %d",&AD[i],&BD[i], &DD[i]);
    /*
            cout<<N<<" "<<ML<<" "<<MD<<endl;
            for(int i=0;i<ML;++i)   cout<<AL[i]<<" "<<BL[i]<<" "<<DL[i]<<endl;
            for(int i=0;i<MD;++i)   cout<<AD[i]<<" "<<BD[i]<<" "<<DD[i]<<endl;
    */
    
            fill(d, d+N, INF);
            d[0] = 0;
    
            //用Bellman-Ford计算d
            for(int k = 0; k < N; ++k){
        
    
                    //从 i+1 到 i 的权值为 0
                    for(int i = 0; i + 1 < N; ++i)
                            if( d[i + 1] < INF)
                                    d[i] = min(d[i], d[i + 1]);
    
                    //从 AL 到 BL 的权值为 DL
                    for(int i = 0; i < ML; ++i)
                            if(d[ AL[i] - 1 ] < INF)
                                    d[ BL[i] - 1 ] = min(d[ BL[i] - 1 ], d[ AL[i] - 1 ] + DL[i]);
    
                    //从 BD 到 AD 的权值为 -DD
                    for(int i = 0; i < MD; ++i)
                            if(d[ BD[i] - 1 ] < INF)
                                    d [AD[i] - 1 ] = min(d[ AD[i] - 1 ], d[ BD[i] - 1 ] - DD[i]);
            }
    
    
            int res = d[N-1];
    
            if(d[0] < 0)    res = -1;  //存在负圈则无解
            else if(res == INF)     res = -2;
    
            printf("%d\n",res);
    
    
            return 0;
    }

[Layout]: http://poj.org/problem?id=3169
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]: /images/20211201/08dca7e82b4549738d9ddba526699da1.png