洛谷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;
}