洛谷P4878 [USACO05DEC]Layout G 题解

题目链接：P4878 [USACO05DEC]Layout G

题意：按编号排了 \(n\) 只奶牛，有的奶牛间必须相距小于等于一个距离，有的奶牛间必须相距大于等于一个距离，问 \(1\) 到 \(n\) 的距离最大值

我们可以发现题目给的数据本质上就是 \(v-u\ge d_i\) 或 \(v-u \le d_i\)

这是什么？差分约束！

差分约束：根据三角不等式 \(d_u + w(u,v) \ge d_v\) 的构成，我们可以把形如 \(v-u\ge d_i\) 的不等式转化为

\(v-d_i\ge u\) （可以看作 \(v\) 向 \(u\) 连了一条边权为 \(-d_i\) 的有向边），同理 \(v-u \le d_i\) 转化为 \(u+d_i \ge v\)

这里不过多讲解差分约束了

那么为什么差分约束后求最短路就是最大值呢？

因为求最短路是由无穷大向下不断约束得到的，因此得到的是最大值（同理求最长路就是最小值）

那我们只要按题意建图就行了

要注意的是，每个奶牛 \(i\) 满足 \(d_{i-1} \le d_{i}\) ，其中 \(d\) 表示所在位置，因此相邻的也要建边

为什么要强调这一点呢？

如下图：

如果没有建边，会发现答案为 \(5\) （如上图所示）

如果建了边，答案才正确（该情况无解）

那现在只要从 \(1\) 开始跑SPFA就好了

但是还有问题， \(1\) 并不能保证与所有结点连通，而我们知道差分约束无解的情况就是图中有负环

这个问题好解决，我们先在原图上建一个超级结点 \(0\) 与所有结点相连（边权为 \(0\) ），在 \(0\) 跑一次SPFA判断即可判断解的情况

说了这么多，是不是有点晕（

理一下思路：

1. 差分约束建图
2. 相邻编号建图
3. 建 \(0\) 结点判断解的情况
4. 有解则从 \(1\) 开始跑SPFA

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e3+5)
#define MAXM (int)(2e4+5)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>inline void read(R T &k)
{
	R char ch=getchar();R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	k=x*f;
}
int n,ml,md,m,d[MAXN],vis[MAXN],cnt[MAXN];
struct Edge
{
	int u,v,w,next;
}e[MAXM<<1];
int head[MAXN],pos=1;
void add(R int u,R int v,R int w)
{
	e[pos]={u,v,w,head[u]};
	head[u]=pos++;
}
bool spfa(R int st)
{
	queue<int> q;q.push(st);
	memset(d,0x3f,sizeof(d));
	vis[st]=1;d[st]=0;cnt[st]=1;
	while(!q.empty())
	{
		R int u=q.front();
		q.pop();vis[u]=0;
		for(R int i=head[u]; i; i=e[i].next)
		{
			R int v=e[i].v,w=e[i].w;
			if(d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				if(!vis[v])
				{
					if(++cnt[v]>n) 
						return 0; // 有0结点，结点数增加1，判负环略有区别 
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return 1;
}
signed main()
{
	read(n);read(ml);read(md);
	for(R int i=1,u,v,w; i<=ml; i++)
	{
		read(u);read(v);read(w); // d_v-d_u<=w -> d_v<=d_u+w
		add(u,v,w);
	}
	for(R int i=1,u,v,w; i<=md; i++)
	{
		read(u);read(v);read(w); // d_v-d_u>=w -> d_v-w>=d_u
		add(v,u,-w);
	}
	for(R int i=1; i<n; i++)
		add(i+1,i,0); // d_i<=d_{i+1}+0
	for(R int i=1; i<=n; i++)
		add(0,i,0);
	if(!spfa(0))return puts("-1"),0;
	spfa(1);
	if(d[n]==INF)puts("-2");
	else printf("%lld\n",d[n]);
	return 0;
}