History

作者：承君阳

关键词：区间 差分约束 最短路

题目简述

有$n$个王朝，采用不同的纪年法，每个王朝有$m_i$帝王，给出每个帝王统治的始末时间$dynasties$，现已知若干场战争分别在某王朝某帝和另一王朝某帝间发生，问其他一些帝王间发生战争的可能性。

$2 \leq n \leq 26;2 \leq m_i \leq 11; 1 \leq dynasties[i][j] \leq 99999;$ $1 \leq |battles|,|queries| \leq 50.$

算法

假设存在一个标准纪年法，每个王朝纪年法与标准纪年法之间的差用$x_i$表示，则每个帝王统治的时间是一个含变量的区间，而一场战争发生则表明两个区间有交，显然，两个区间有交的充要条件是一个区间的右端点$\geq$另一个区间的左端点，即$x_i \geq x_j+y$且$x_j \geq x_i+z$，我们用$f[i][j]$表示$x_i$至少比$x_j$多多少，用Floyd传递约束后直接判断即可。

时间复杂度为$O(n^3)$。