Acwing 1170. 布局
题意
当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。
农夫约翰有 N 头奶牛，编号从 1 到 N，沿一条直线站着等候喂食。
奶牛排在队伍中的顺序和它们的编号是相同的。
因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。
如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。
另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D
给出 M L条关于两头奶牛间有好感的描述，再给出 M D 条关于两头奶牛间存有反感的描述。
你的工作是：如果不存在满足要求的方案，输出 −1；如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出 −2；否则，计算出在满足所有要求的情况下，1 号奶牛和N 号奶牛间可能的最大距离。
思路
设一组变量 x i 表示 第 i 只奶牛所在的位置，因为题目要求奶牛按照编号的顺序站，所以会有以下不等式约束条件：
① x i ≤ x i + 1 同时，根据M L 和 M D 的约束，会有以下不等式约束条件
② x b − x a ≤ L 其中 x a ≤ x b
③ x b − x a ≥ D 其中 x a ≤ x b
因为奶牛之间只有相对关系，没有绝对关系，也即某一个奶牛在数轴上的具体位置不重要，只需要满足不等式的约束条件即可。因为题目要求最大距离，所以应该用差分约束的最短路模型。
因为题目不需要求出每个奶牛具体的位置，所以无需添加绝对关系不等式。
首先考虑问题1，不满足要求即图中存在负环。
问题2、3：1 号奶牛和 N 号奶牛之间的距离可以任意大等价于，从 1 到 N 的最短路可以无限大，所以从1 求一遍最短路判断 d[n] 是否等于 INF 即可，如果 == INF 说明距离可以任意大，否则d[n]即为求出最大的距离。
考虑这样一个问题：为什么判断是否满足条件时需要将所有点 push 进队列，而求最大距离时，只需要将 节点 1 push 进队列？
是否满足条件 == 图中是否存在负环 如果只把 1 push 进队列，1 可能到达不了所有的点，所以要把所有点 push进去
1 到 N 的最大距离，经典的最短路问题，所以只需要把起点 push 进队列，无需考虑是否能到达所有的点。
代码
// Author：zzqwtcc // Problem: 排队布局 // Contest: AcWing // Time：2021-10-29 19:16:45 // URL: https://www.acwing.com/problem/content/1172/ // Memory Limit: 64 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) // #define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;} template<typename T>void debug(T t){cerr << t << endl;} template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;} template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;} // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1010,M = 2e4 + N + 10; int n; int m1,m2; int h[N],e[M],ne[M],w[M],idx; int cnt[N],d[N]; 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(d,0x3f,sizeof d); memset(cnt,0,sizeof cnt); memset(st,0,sizeof st); queue<int>q; for(int i = 1; i <= size;++i){ q.push(i); d[i] = 0; } while(q.size()){ int u = q.front(); q.pop(); st[u] = false; for(int i = h[u];~i;i = ne[i]){ int j = e[i]; int dis = w[i]; if(d[j] > d[u] + dis){ d[j] = d[u] + dis; cnt[j] = cnt[u] + 1; if(cnt[j] >= n)return false; if(!st[j]){ st[j] = true; q.push(j); } } } } return true; } void solve() { cin >> n >> m1 >> m2; memset(h,-1,sizeof h); while(m1--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); if(a > b)swap(a,b); add(a,b,c); } while(m2--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); if(a > b)swap(a,b); add(b,a,-c); } for(int i = 1; i <= n - 1;++i){ add(i + 1,i,0); } if(!spfa(n))puts("-1"); else { spfa(1); if(d[n] == INF)puts("-2"); else printf("%d\n",d[n]); } } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
