| 题目名称 | 1117. [WC 2010模拟] 奶牛排队 |
|---|---|
| 输入输出 | layout.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-10-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：213， 提交：469， 通过率：45.42% | ||||
 可以的. |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
 用ۣۣۣۣۣۣۣۣۣۣۣۣۣۣۣ |
100 | 0.000 s | 0.00 MiB | C++ |
 槿柒 |
100 | 0.000 s | 0.00 MiB | C++ |
 面对疾风吧 疾风 疾风吧 |
100 | 0.000 s | 0.00 MiB | C++ |
 Moonler |
100 | 0.000 s | 0.00 MiB | C++ |
 乐未殇 |
100 | 0.000 s | 0.00 MiB | C++ |
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 111 |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
| 本题关联比赛 | |||
| 4043级NOIP2022欢乐赛2nd | |||
| 关于 奶牛排队 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
吊
┭┮﹏┭┮
2024-01-13 17:59
14楼
| ||||
|
所有测试数据似乎都是先编号小的边再编号大的边，我把swap函数删掉了也没错哎
| ||||
|
SPFA怎么改都慢成翔...
算了...还是用原来的写法吧... | ||||
|
SPFA判负环应该是用点的入队次数，我用边的松弛次数判断也A了
 liu_runda
2016-08-03 18:06
10楼
| ||||
|
233
 SOBER GOOD BOY
2016-08-03 16:42
9楼
| ||||
|
膜拜楼上神犇
Orz SOBER GOOD BOY
2016-08-03 16:34
8楼
| ||||
|
不会查分约束的我就这样写出来人生第一发查分约束= =
还有为啥我的SPFA这么慢... 顺便膜拜楼下下下神犇...虽然我知道对于更一般的情况Dijkstra是跑不了的... 对于这个题如此简单的情况确实可以用Dijkstra...... 另外用Bellman-Ford或者SPFA判负环变得很容易... | ||||
|
果然，我就知道Dijkstra也能做查分约束，处理负边，hhh
 _Itachi
2016-08-03 16:30
6楼
| ||||
|
回复 @叶子の宿敌 :
Spfa写错了没T算你好运呵呵大 | ||||
ShallowDream雨梨
AntiLeaf【题目描述】
像每个人一样，奶牛们喜欢在排队等待领取食物和自己的朋友站在一起。$FJ$ 拥有 $N$ 头奶牛，编号为 $1$ 至 $N$ 。它们站成一行，等待 $FJ$ 派送奶牛营养餐。这些奶牛按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多头奶牛挤在同一位置的情况(也就是说，如果我们认为奶牛位于数轴上，那么多头奶牛的位置坐标可能相同)。
某些奶牛之间互相喜欢，它们希望互相之间的距离至多为一个定值。某些奶牛之间互相厌恶，它们希望互相之间的距离至少为一个定值。现在给定 $X$ 个互相喜爱的奶牛对以及它们之间距离的最大值， $Y$ 个互相厌恶的奶牛对以及它们之间距离的最小值。
你的任务是计算在满足以上条件的前提下，编号为 $1$ 和编号为 $N$ 的奶牛之间距离的最大可能值。
【输入格式】
输入文件第一行三个整数 $N$ , $X$ 以及 $Y$ 。
此后 $X$ 行，每行包含三个用空格分开的整数 $A , B$ 和 $D$，其中 $A , B$ 满足 $A \lt B$。表示编号为 $A$ 和 $B$ 的奶牛之间的距离至多为 $D$。
此后 $Y$ 行，每行包含三个用空格分开的整数 $A , B$ 和 $D$ ，其中 $A , B$ 满足 $A \lt B$。表示编号为 $A$ 和 $B$ 的奶牛之间的距离至少为 $D$。
【输出格式】
输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出 $-1$。如果编号 $1$ 和编号 $N$ 的奶牛间距离可以任意，就输出 $-2$ 。否则输出它们之间的最大可能距离。
【样例输入1】
4 2 1 1 3 10 2 4 20 2 3 3
【样例输出1】
27
【样例输入输出2】
点击下载样例2
【数据规模与约定】
对于 $20\%$ 的数据，$1 \leq N,X,Y \leq 20 , 1 \leq D \leq 3000$;
对于 $40\%$ 的数据，$1 \leq N \leq 100,1 \leq X,Y \leq 400 , 1 \leq D \leq 31000$;
对于 $100\%$ 的数据，$1 \leq N \leq 1000,1 \leq X,Y \leq 5000 , 1 \leq D \leq 500000$;
【来源】
中小学电脑报 NOI导刊 NOIP2012河南省实验中学培训 Day4 Exercise Problem 10