P4878 [USACO05DEC] 布局

    • 458通过
    • 2K提交
  • 题目提供者 qq1010903229
  • 评测方式 云端评测
  • 标签 差分 差分约束 最短路 USACO 2005
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

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

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

    给出 $M_L$ 对好基友的编号,以及它们希望彼此之间的距离小于等于多少;又给出 $M_D$ 对情敌的编号,以及它们希望彼此之间的距离大于等于多少 $(1\le 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$ 号奶牛间的最大距离。

    题目背景

    13组数据,前10组为原数据,后3组为hack数据

    题目描述

    Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).

    Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

    Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

    输入输出格式

    输入格式:

    Line 1: Three space-separated integers: N, ML, and MD.

    Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.

    Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.

    输出格式:

    Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.

    输入输出样例

    输入样例#1: 复制
    4 2 1
    1 3 10
    2 4 20
    2 3 3
    输出样例#1: 复制
    27

    说明

    Explanation of the sample:

    There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.

    The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。