T15463 人心丑恶的妹子们[来自光棍的呐喊]

题目背景

Rikka 喜欢将他的妹纸们排成一队。

题目描述

假设他拥有 N 只妹纸,编号为 1 至 N。Ls 让他们

站成一行,等待自己来派送营养餐。这些妹纸按照编号大小排列,并且由于它们都很想

4 早点吃饭,于是就很可能出现多只妹纸挤在同一位置的情况(也就是说,如果我们认为

妹纸位于数轴上,那么多只妹纸的位置坐标可能相同)。

因为众所周知的原因,某些妹纸之间互相喜欢,他们希望互相之间的距离至多为一

个定值。但某些妹纸之间互相厌恶,他们希望互相之间的距离至少为一个定值。现在给

定 ML 个互相喜爱的妹纸对以及他们之间距离的最大值,MD 个互相厌恶的妹纸对以及

他们之间距离的最小值。

你的任务是计算在满足以上条件的前提下,帮助 Ls 计算出编号为 1 和编号为 N 的

妹纸之间距离的最大可能值。

输入输出格式

输入格式:

输入文件为layout.in。

第一行有3 个整数,每两个整数之间用一个空格隔开,依次表示n,ML 和 DL;

此后 ML 行,每行包含三个用空格分开的整数 A,B 和 D,其中 A,B 满足 1<=A<=B<=N。

表示编号为 A 和 B 的妹纸之间的距离至多为 D。

此后 MD 行,每行包含三个用空格分开的整数 A,B 和 D,其中 A,B 满足 1<=A<=B<=N。

表示编号为 A 和 B 的妹纸之间的距离至少为 D。

输出格式:

输出文件名为 layout.out。

输出文件仅包含一个整数。如果不存在任何合法的排队方式,就输出-1。如果编号

1 和编号 N 的妹纸间距离可以任意,就输出-2 。否则输出他们之间的最大可能距离。

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

对于 40%的数据,N<=100;

对于 100%的数据,N<=1000;ML,MN<=10000;D<=1000000。

差分约束系统模板题。

我竟然一年没学过这个,Sad…

就是说有多个形如

d[x] – d[y] <= w的条件,求某两个间的距离最大值。

移向可得 d[x] <= d[y] + w,然后就是最短路式子的形式,最大值即为min(d[x],d[y] + w),可以看出可以跑最短路得到。

那么同理:d[x] -d[y] >= w可以*-1,得到 d[y] – d[x] <= -w,一样建图。

搞定。

c++代码如下:

 

9 + 2 =