排队布局 & 布局 Layout

差分约束 虚拟源点 T4 #10090. 「一本通 3.4 练习 2」布局 Layout - 题目 - LibreOJ (loj.ac)

原题来自：USACO 2005 Dec. Gold

FJ 有 N 头奶牛 $(2\le N\le 1000)$，编号为 $1\dots N$。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设 $i$ 号奶牛位于 $P_i$，则 $P_1\le P_2\le \dots \le P_N$。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 $(1\le M_L,M_D\le 10^4)$。

请计算：如果满足上述所有条件，$1$ 号奶牛和 $N$ 号奶牛之间的距离$（P_N-P_1）$最大为多少。

输入格式

第一行：三个整数 $N,M_L,M_D$，用空格分隔。
第 $2\dots M_L+1$ 行：每行三个整数 $A,B,D$，用空格分隔，表示 $P_B-P_A\le D$。
第 $M_L+2\dots M_L+M_D+1$ 行：每行三个整数 $A,B,D$，用空格分隔，表示 $P_B-P_A\ge D$。
保证 $1\le A<B\le N,1\le D\le 10^6$。

输出格式

一行，一个整数。如果没有合法方案，输出 $\text{-1}$. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 $\text{-2}$. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

样例

输入

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

输出

27

数据范围

对于全部数据，$2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6$。

思路

设$S_i$ 为 $1-i$ 的距离, 可以根据题目得出一些系列不等式：

1. $S_i\le S_{i+1}$
2. $S_b-S_a\ge M_D$, 即 $S_a+M_D\le S_b$
3. $S_b-S_a\le M_L$ , 即 $S_b-M_L\le S_a$

再检验当前0点是否可以到达所有点, 因为条件一是从 $i+1\to i$ , 故从0点不能到达所有点, 可以假设一个无限远地方有一个点, 连到所有点的权值为0, 也就是定义一个虚拟源点。实际上我们也不需要真的建边, 只需要在SPFA时把所有点加入队列中就行。

题目要求先判断负环, 那么需要把所有点加入其中。 然后判断是否可以无穷远, 图论中对应无穷远就是不存在从1到n的边, 我们只需要再做一次从1出发的SPFA即可, 若$dist[n]\ge \frac{0x3f3f3f3f3f}{2}$ 则输出-2。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e3 + 10, M = 3e6;
int h[N], e[M], w[M], ne[M], idx;
typedef long long LL;
LL dist[N];
int q[N], cnt[N];
int n, m1, m2;
bool st[N];
 
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
 
bool spfa(int size)
{
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = 0;
    for (int i = 1; i <= size; i++)
    {
        q[tt++] = i;
        dist[i] = 0;
        st[i] = true;
    }
    while (hh != tt)
    {
        int t = q[hh++];
        if (hh == N)
            hh = 0;
        st[t] = false;
 
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1)
                    return false;
                if (!st[j])
                {
                    st[j] = true;
                    q[tt++] = j;
                    if (tt == N)
                        tt = 0;
                }
            }
        }
    }
    return true;
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m1 >> m2;
    for (int i = 1; i < n; i++)
        add(i + 1, i, 0);
 
    while (m1--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    while (m2--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(b, a, -c);
    }
 
    if (!spfa(n))
        cout << -1 << endl;
    else
    {
        spfa(1);
        if (dist[n] >= 0x3f3f3f3f / 2)
            cout << "-2" << endl;
        else
            cout << dist[n] << endl;
    }
 
    return 0;
}