$$\color{Purple}{kuangbin题解目录}$$
描述
当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。
农夫约翰有 $N$ 头奶牛,编号从 $1$ 到 $N$,沿一条直线站着等候喂食。
奶牛排在队伍中的顺序和它们的编号是相同的。
因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。
如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数 $L$。
另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数 $D$。
给出 $M_L$ 条关于两头奶牛间有好感的描述,再给出 $M_D$ 条关于两头奶牛间存有反感的描述。
你的工作是:如果不存在满足要求的方案,输出-1;如果 $1$ 号奶牛和 $N$ 号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,$1$ 号奶牛和 $N$ 号奶牛间可能的最大距离。
输入格式
第一行包含三个整数 $N,M_L,M_D$。
接下来 $M_L$ 行,每行包含三个正整数 $A,B,L$,表示奶牛 $A$ 和奶牛 $B$ 至多相隔 $L$ 的距离。
再接下来 $M_D$ 行,每行包含三个正整数 $A,B,D$,表示奶牛 $A$ 和奶牛 $B$ 至少相隔 $D$ 的距离。
输出格式
输出一个整数,如果不存在满足要求的方案,输出-1;如果 $1$ 号奶牛和 $N$ 号奶牛间的距离可以任意大,输出-2;否则,输出在满足所有要求的情况下,$1$ 号奶牛和 $N$ 号奶牛间可能的最大距离。
数据范围
$2 \\le N \\le 1000$,
$1 \\le M_L,M_D \\le 10^4$,
$1 \\le L,D \\le 10^6$
输入样例:
4 2 1
1 3 10
2 4 20
2 3 3
输出样例:
27
思路
- 该题可转化为
差分约束
解决,求$1$到$n$的最大距离(最大值
),跑单源最短路
,差分不等式用小于
关系.- 题目已知
后面的牛的位置一定不能比前面的靠前
(即第$i+1$头牛应大于第$i$头牛的位置),用不等式表示为$x_{i+1} \ge x_{i}$,适当变形成小于
关系$x_{i}\le x_{i+1}+0$,建立$i+1$到$i$,长度为$0$的边.- 其次已知存在牛$a$和牛$b$,假设$a$的位置小于$b$的位置,两者之间的距离
不超过
一个给定的数$L$,用不等式表示为$x_b-x_a \le L$,适当变形成小于
关系,$x_b \le x_a+L$,建立$x_a$到$x_b$,长度为$L$的边.- 同理已知存在牛$a$和牛$b$,假设$a$的位置小于$b$的位置,两者间的距离
不小于
一个给定的数$D$,用不等式表示为$x_b-x_a \ge D$,适当变形成小于
关系,$x_a \le x_b-D$,建立$x_b$到$x_a$,长度为$D$的边.
该题可设立虚拟源点
$0$,即$x_i \le x_0 +0$,建立$x_0$到$x_i$,长度为$0$的边.
最后用spfa算法
跑最短路.- 该题中先用
虚拟源点
跑spfa算法
判是否存在满足要求的方案
,若满足,则跑从起点$1$出发到$n$的单源最短路
,若无法到达$n$输出-2
,反之输出最短路
的结果即可.
代码
// Problem: 排队布局
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1172/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-08 16:57:22
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1010
#define MAXM 22010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m,k;
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int dist[MAXN],vis[MAXN],cnt[MAXN];
int spfa(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int> q;
q.push(start);
vis[start]=1;
dist[start]=0;
while(q.size()>0)
{
int temp=q.front();
q.pop();
vis[temp]=0;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
if(dist[j]>dist[temp]+val[i])
{
dist[j]=dist[temp]+val[i];
cnt[j]=cnt[temp]+1;
if(cnt[j]>=n)//存在负环
return 1;
if(vis[j]==0)
{
q.push(j);
vis[j]=1;
}
}
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> m >> k;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
if(i<=n-1)
add(i+1,i,0);//x_{i+1}>=x_{i}-->x_{i}<=x_{i+1}+0
add(0,i,0);//x_{i}<=x_{0}+0
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin >> a >> b >> c;
if(a>b)
swap(a,b);
add(a,b,c);//x_b-x_a<=L-->x_b<=x_a+L
}
for(int i=1;i<=k;i++)
{
int a,b,c;
cin >> a >> b >> c;
if(a>b)
swap(a,b);
add(b,a,-c);//x_b-x_a>=D-->x_a<=x_b-D;
}
if(spfa(0)==1)
cout << -1 << endl;
else
{
spfa(1);
if(dist[n]==inf)
cout << -2 << endl;
else cout << dist[n] << endl;
}
return 0;
}