题解 P4878 【[USACO05DEC]layout布局】

> ~~这是我们学校的小网管上传的题，我居然来写题解了QWQ~~ 很显然，这是一道差分约束的裸题，瞎搞一下跑个最短路就可以了，但是~~丧心病狂~~的小网管出了三个~~DB~~数据，你还得去从0开始跑spfa判断图是不是联通的，然后就A了QAQ ## 差分约束 这玩意主要就是给你几个不等式，让你求一个东西的范围， $x_2-x_1\leq a_1$ $x_3-x_2\leq a_2$ $x_4-x_3\leq a_3$ $x_5-x_4\leq a_4$ 比方说我们有以上几个不等式，求 $x_5-x_1$的最大值，直接代入计算就可以，但是要计算机能拿来计算，我们得有一个规矩点的方法 我们可以通过移项，发现 $x_i\leq x_j +a_k$ 然后可以~~自然而然~~地想到求最短路时的松弛操作，但是这里符号是反的，这并无大碍，因为我们是求 $x_5-x_1$ 的最大值，就等于 $x_1$ ~ $x_5$ 的最小值（这里请好好理解），如果 $dis[n]$ 是无穷大，就表明 $x_5-x_1$ 可以无穷大，如果出现负环，就表明无解 ## code： 方便~~复制~~的代码QWQ ```cpp #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define main mian using namespace std; const int N=1005; const int M=40005; int n,ml,md,a,b,d; struct EDGE { int nxt,to,wei,; }edge[M]; int head[N],tot; inline void add(int x,int y,int v) { edge[++tot].nxt=head[x]; edge[tot].to=y; edge[tot].wei=v; head[x]=tot; } queue<int> q; int vis[N],dis[N],circle[N]; void spfa(int s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(circle,0,sizeof(circle)); q.push(s); vis[s]=1,dis[s]=0; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i;i=edge[i].nxt) { int tt=edge[i].to; if(dis[now]+edge[i].wei<dis[tt]) { dis[tt]=dis[now]+edge[i].wei; circle[tt]=circle[now]+1; if(circle[tt]>=n) { puts("-1");exit(0); } if(!vis[tt]) { vis[tt]=1; q.push(tt); } } } } } int main() { int n; scanf("%d%d%d",&n,&ml,&md); for(int i=1;i<=n;i++) add(0,i,0); for(int i=1;i<=ml;i++) { scanf("%d%d%d",a,b,d); add(a,b,d); } for(int i=1;i<=md;i++) { scanf("%d%d%d",a,b,d); add(b,a,-d); } spfa(0); spfa(1); if(dis[n]==INF) puts("-2"); else printf("%d",dis[n]); return 0; } ```