题目描述
当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。
农夫约翰有 N 头奶牛,编号从 1 到 N,沿一条直线站着等候喂食。
奶牛排在队伍中的顺序和它们的编号是相同的。
因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。
如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数 L。
另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数 D。
给出 $M_{L}$ 条关于两头奶牛间有好感的描述,再给出 $M_{D}$ 条关于两头奶牛间存有反感的描述。
你的工作是:如果不存在满足要求的方案,输出-1;如果 1 号奶牛和 N 号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1 号奶牛和 N 号奶牛间可能的最大距离。
算法1
差分约束
假定第i头牛的坐标用x~i~表示,由于每头牛都按照编号顺序排序,于是有:$x_{i+1}\le x _{i}+0 (i\in \left [ 1,n \right ) )$
前M~L~行输入A,B,L表示A和B至多间隔L的距离(假定A<B),$x_{B}\le x_{A}+L$
M~D~行输入A,B,D表示A和B至少间隔D的距离(假定A<B),有$x_{A}\le x_{B}-D$
根据上述不等式组可以得到一个图,其中x~n~能遍历到所有的边,所以x~n~可以作为超级源点。
- 从n出发做一遍最短路,如果存在负环,则说明无解,输出-1
- 从1出发做一遍最短路(即固定1号点在坐标为0的位置),求出每个点到1的最短路径,其中每一天到i号点的路径都表示一个不等式链 x~i~≤c~k~,可以从所有c中找到最小值,即为x~i~所能取到的最大值,如果此时x~n~为INF,则表示距离可以无限大 输出-2
- 否则输出dis[n]
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M = 21010,INF = 0x3f3f3f3f;
int h[N],ne[M],e[M],w[M],idx;
int dis[N];
int cnt[N];
bool st[N];
int n,m1,m2;
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa(int x){
memset(dis,0x3f,sizeof dis);
memset(st,false,sizeof st);
memset(cnt,0,sizeof cnt);
queue<int> q;
dis[x] = 0;
q.push(x);
st[x] = true;
while(!q.empty()){
int t = q.front();
q.pop();
st[t] = false;
for(int i=h[t];i != -1;i = ne[i]){
int j = e[i];
if(dis[j]>dis[t] + w[i]){
dis[j] = dis[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j]>=n) return false;
if(!st[j]){
st[j] = true;
q.push(j);
}
}
}
}
return true;
}
int main(){
cin>>n>>m1>>m2;
memset(h,-1,sizeof h);
while(m1--){
int a,b,c;
cin>>a>>b>>c;
if(a>b) swap(a,b);
add(a,b,c);
}
while(m2--){
int a,b,c;
cin>>a>>b>>c;
if(a>b) swap(a,b);
add(b,a,-c);
}
for(int i=1;i<n;i++) add(i+1,i,0);
if(!spfa(n)) puts("-1");
else{
spfa(1);
if(dis[n] == INF) puts("-2");
else cout<<dis[n];
}
return 0;
}