CFGYM102394A CCPC2019哈尔滨A Artful Paintings

然后据此建边，其中$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;
}