洛谷P4878 [USACO05DEC]layout布局

题目描述

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。\(FJ\) 有编号为 \(1\dots N\) 的 \(N\) 头奶牛 \((2\le N\le 1000)\)。开始时，奶牛们按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 \(M_L\) 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 \(M_D\) 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 \((1≤M_L, M_D\le 10^4)\)

请计算：如果满足上述所有条件，\(1\) 号奶牛和 \(N\) 号奶牛之间的距离最大为多少。

输入输出格式

输入格式

第一行：三个整数 \(N, M_L, M_D\)，用空格分隔。

第 \(2\dots M_L+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(A\) 号奶牛与 \(B\) 号奶牛之间的距离须 \(\le D\)。保证 \(1\le A<B\le N\), \(1\le D\le 10^6\).

第 \(M_L+2\dots M_L+M_D+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(A\) 号奶牛与 \(B\) 号奶牛之间的距离须 \(\ge D\)。保证 \(1\le A<B\le N\), \(1\le D\le 10^6\).

输出格式

一行，一个整数。如果没有合法方案，输出 \(-1\). 如果有合法方案，但 \(1\) 号奶牛可以与 \(N\) 号奶牛相距无穷远，输出\(-2\). 否则，输出 \(1\) 号奶牛与 \(N\) 号奶牛间的最大距离。

输入输出样例

输入样例#1：

输出样例#1：

思路：

做这道题之前，大家应该先学习一下差分约束。

给大家推荐个博客：不是我的……

然后回到这个题目上来，首先这道题有负环的出现，那显然不能用\(dijkstra\)了，那就把解法锁定为\(spfa\)。

对于给出的前\(M_L\)种关系：

就是这个样子：\(d[B]-d[A] \leq D\)

后\(M_D\)种关系是：\(d[B]-d[A] \geq D\),即\(d[A]-d[B] \leq -D\)

那对于第一种关系，根据差分约束，我们需要建从\(A\)到\(B\)，边权为D的边，对于第二种关系，我们就需要建从\(B\)到\(A\)，边权为\(-D\)的边。

这样建完图跑直接调用\(spfa(1)\)就可以得\(70\)分了，那为什么不能\(AC\)

呢？

因为我们差分约束时的起点是\(0\)，所以我们要先跑一遍\(spfa(0)\),并建一条从0到\(i(1 \leq i \leq n)\)的边权为0的边，为什么呢？

难道不应该是\(d[0]-d[i] \leq 0\)么？这样不是应该从i到0的边么？但是，有没有想过，如果你这样建，那你以0为起点跑spfa有意义么？0没法到达任何一个点，所以，我们需要建一条从0到i的边的边权为0的边。这样这题就能AC啦！

自己整理的题解

下面是我丑陋(学长说的)的代码：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<queue>

#define maxn 1007

using namespace std;

int num,n,m,p,head[maxn],dis[maxn],vis[maxn],in[maxn];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

struct node {

  int v,w,nxt;

}e[20007];

inline void ct(int u, int v, int w) {

  e[++num].v=v;

  e[num].w=w;

  e[num].nxt=head[u];

  head[u]=num;

}

const int inf=0x3f3f3f3f;

inline void spfa(int s) {

  memset(dis,0x3f,sizeof(dis));

  memset(vis,0,sizeof(vis));

  memset(in,0,sizeof(in));

  queue<int>q;

  q.push(s),vis[s]=1,in[s]=1;

  dis[s]=0;

  while(!q.empty()) {

    int u=q.front();

    q.pop();vis[u]=0;

    for(int i=head[u];i;i=e[i].nxt) {

      int v=e[i].v;

      if(dis[v]>dis[u]+e[i].w) {

        dis[v]=dis[u]+e[i].w;

        if(!vis[v]) {

          vis[v]=1;

          in[v]++;

          if(in[v]>n) {

            printf("-1\n");

            exit(0);

          }

          q.push(v);

        }

      }

    }

  }

}

int main() {

  n=qread(),m=qread(),p=qread();

  for(int i=1,u,v,d;i<=m;++i) {

    u=qread(),v=qread(),d=qread();

    ct(u,v,d);

  }

  for(int i=1,u,v,d;i<=p;++i) {

    u=qread(),v=qread(),d=qread();

    ct(v,u,-d);

  }

  for(int i=1;i<=n;++i) ct(0,i,0);

  spfa(0);

  spfa(1);

  if(dis[n]==inf) {

    printf("-2\n");

    return 0;

  }

  printf("%d\n",dis[n]);

  return 0;

}

巴特西