一眼看过去是差分约束板子题，实际上也就是差分约束板子题。
首先这个题可以对答案进行二分。如果铺x个可行，那么x+1个显然可行，所以我们先二分确定一个x。
然后我们的题目转变成了，能不能在恰好铺x个的情况下构造一组合法方案，根据最短路的松弛条件可知，不等式$x_a+v\leq x_b$等价于从a到b，边权为$-v$的边（最短路存在时，令$x_a$表示源点到a的距离，$x_b$同理，那么$x_a$和$x_b$在作为未知变量的时候一定是满足上述不等式的。）
所以我们可以得到，需要建立以下六种不等式：
1. $x_{n-1}+0\leq x_n$(前缀和不减)
2. $x_n+(-1)\leq x_{n-1}$前缀和要么加1要么不变
3. $x_{l-1}+x\leq x_r$ 区间染色数下限
4. $x_r +(x-M) \leq x_{l-1}$ 区间外染色数下限
5. $x_0+M\leq x_n$ 一共至少染M个
6. $x_n+(-M)\leq x_0$ 一共至多染M个(与5一起保证恰好染M个)
然后据此建边，其中$M$是我们二分的铺的个数。建出来的图跑一个从n到0的最短路，如果最短路存在（即没有负环），那说明M可行，答案可以考虑进一步缩小。如果存在负环，则说明M不可行。
但是这里的SPFA要注意优化，大概需要一个SLF（Small Label First），即如果待入队节点的已知最短距离小于队列头部节点，则把他扔到队列头部。
然后别用long long，跑的有点慢。
#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using int_t = int;
/*
1. x_{n-1}+0<=x_n(前缀和不减)
2. x_n+(-1)<=x_{n-1}前缀和要么加1要么不变
3. x_{l-1}+x<=x_r 区间染色数下限
4. x_r +(x-M) <= x_{l-1} 区间外染色数下限
5. x_0+M<=x_n 一共至少染M个
6. x_n+(-M)<=x_0 一共至多染M个(与5一起保证恰好染M个)
*/
const int_t LARGE = 3010;
const int_t INF = 0x3fffffff;
int_t dis[LARGE + 1];
int_t inqN[LARGE];
bool inqueue[LARGE + 1];
struct Edge {
int_t to, weight;
Edge(int_t v, int_t w) : to(v), weight(w) {}
};
struct Limitation {
int_t left, right, val;
} cond1[LARGE + 1], cond2[LARGE + 1];
int_t n, m1, m2;
//不等式A+X<=B变为边(A,B)，长度-X
std::vector<Edge> graph[LARGE + 1];
void clear() {
std::fill(dis, dis + 1 + n, INF);
std::fill(inqueue, inqueue + 1 + n, false);
std::fill(inqN, inqN + 1 + n, 0);
for (int_t i = 0; i <= n; i++)
graph[i].clear();
}
void pushEdge(int_t u, int_t v, int_t w) {
#ifdef DEBUG
cout << "edge " << u << " to " << v << " val " << w << endl;
#endif
graph[u].push_back(Edge(v, w));
}
//添加不等式x_a+v<=x_b
void pushLEQ(int_t a, int_t b, int_t v) {
#ifdef DEBUG
cout << "cond x_" << a << " + " << v << " <= x_" << b << endl;
#endif
pushEdge(b, a, -v);
}
bool SPFA(int_t src, int_t target) {
std::deque<int_t> queue;
dis[src] = 0;
inqueue[src] = true;
queue.push_back(src);
while (!queue.empty()) {
int_t front = queue.front();
queue.pop_front();
inqueue[front] = false;
inqN[front]++;
if (inqN[front] > n)
return false;
for (const auto& edge : graph[front]) {
if (dis[edge.to] > dis[front] + edge.weight) {
dis[edge.to] = dis[front] + edge.weight;
#ifdef DEBUG
cout << "dis " << edge.to << " to " << dis[edge.to] << endl;
#endif
if (!inqueue[edge.to]) {
if (!queue.empty() && dis[edge.to] < dis[queue.front()])
queue.push_front(edge.to);
else
queue.push_back(edge.to);
inqueue[edge.to] = true;
}
}
}
}
return true;
}
bool check(int_t x) {
#ifdef DEBUG
cout << "checking " << x << endl;
#endif
clear();
for (int_t i = 1; i <= n; i++) {
pushLEQ(i - 1, i, 0);
}
for (int_t i = 1; i <= n; i++) {
pushLEQ(i, i - 1, -1);
}
for (int_t i = 1; i <= m1; i++) {
const auto& ref = cond1[i];
pushLEQ(ref.left - 1, ref.right, ref.val);
}
for (int_t i = 1; i <= m2; i++) {
const auto& ref = cond2[i];
pushLEQ(ref.right, ref.left - 1, ref.val - x);
}
pushLEQ(0, n, x);
pushLEQ(n, 0, -x);
auto ret = SPFA(n, 0);
#ifdef DEBUG
cout << "check " << x << " = " << ret << endl;
#endif
return ret;
}
int main() {
std::ios::sync_with_stdio(false);
int_t T;
cin >> T;
while (T--) {
cin >> n >> m1 >> m2;
for (int_t i = 1; i <= m1; i++) {
auto& ref = cond1[i];
cin >> ref.left >> ref.right >> ref.val;
}
for (int_t i = 1; i <= m2; i++) {
auto& ref = cond2[i];
cin >> ref.left >> ref.right >> ref.val;
}
int_t left = 0, right = n;
int_t result = INF;
while (left + 1 < right) {
int_t mid = (left + right) / 2;
if (check(mid)) {
result = std::min(result, mid);
right = mid - 1;
} else
left = mid + 1;
}
for (int_t i = left; i <= right; i++)
if (check(i))
result = std::min(result, i);
cout << result << endl;
}
return 0;
}