P4878 [USACO05DEC]Layout G(差分约束&最短路)

P4878 [USACO05DEC]Layout G(差分约束&最短路)

思路: 差分约束转最短路。

此题关键是建图和特判。

建图：

因为是求 $max(d[n]-d[1])\rightarrow d[n]-d[1]\leq ans$， $ans$是我们要求的答案，即我们需要让 $ans$最小化，这与最短路中 $若：d[v]>d[u]+w\rightarrow d[v]=d[u]+w$是一致的。

目的是让： $d[v]-d[u]\leq w$，即对于题目限制1中的 $v-u\leq d$。

对于 $v-u\geq w$,直接建图 $add(u,v,w)$。

限制2同理：就是不等式变个号， $add(v,u,-w)$。

此外题目还要求：每头牛按照顺序排好，即： $v-(v+1)\leq 0.$

即： $add(v+1,v,0)$.

特判：

当图不连通时：是有无限多解的，因为没有约束条件。

对于不连通我们可以建立一个超级源点 $0$，将 $0$与每个结点连一条边，然后跑一遍 $spfa$。

当图有负环时：是无解的，因为没有最小值。对此我们只需记录每个结点入队次数，如果大于等于 $n$次，必然有负环。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define fmst(a) memset(a,0x3f,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m1,m2;
int h[N],cnt,vis[N],d[N],in[N];
struct edge{int to,nt,w;
}e[N<<1];
void add(int u,int v,int w){e[++cnt]={v,h[u],w},h[u]=cnt;
} 
int spfa(int st){mst(vis),mst(in),fmst(d);queue<int>q;q.push(st);vis[st]=1,d[st]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=h[u];i;i=e[i].nt){int v=e[i].to,w=e[i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!vis[v]){in[v]++;if(in[v]==n) return -1;//判负环. q.push(v),vis[v]=1;}}} }return d[n]==inf?-2:d[n];//判无解. 
}
int main(){scanf("%d%d%d",&n,&m1,&m2);int u,v,w;for(int i=0;i<=n;i++) add(0,i,0);for(int i=1;i<n;i++) add(i+1,i,0); for(int i=1;i<=m1;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);}for(int i=1;i<=m2;i++){scanf("%d%d%d",&u,&v,&w);add(v,u,-w);}int tmp=spfa(0);if(tmp<=-1) printf("%d\n",tmp);else printf("%d\n",spfa(1));return 0;
}

学习博客：
传送门