SP116 Intervals

差分约束模板。

设$a_i$为$0-i$中出现的数的个数和。

则有以下约束条件.

$$\text{对于一个区间}left,right\\a_{right}-a_{left-1}\ge count\\\text{对于其他下标}\\a_i-a_{i-1}\ge 0\left( \text{保证前缀和} \right) \\a_i\le a_{i-1}+1\rightarrow a_{i-1}-a_i\ge -1\left( \text{两个位置至多差}1 \right) \\\text{然后跑差分约束，最小化}a_n-a_0\text{，求最长路即可。}$$

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 50000;
const int_t SOURCE = 0;
const int_t INF = 0x7fffffff;
struct Edge
{
    int_t to;
    int_t weight;
    Edge(int_t to, int_t weight)
    {
        this->to = to;
        this->weight = weight;
    }
};

struct Processor
{
    std::vector<Edge> graph[LARGE + 1];
    int_t dis[LARGE + 1];
    bool inq[LARGE + 1];
    int_t inqN[LARGE + 1];
    //条件a-b>=val
    void pushLEQ(int_t a, int_t b, int_t val)
    {
        // cout << a << " " << b << " " << val << endl;
        graph[b].push_back(Edge(a, val));
    }
    int_t n;
    int_t max = 0;
    int_t process()
    {
        cin >> n;
        for (int_t i = 1; i <= n; i++)
        {
            int_t left, right, val;
            cin >> left >> right >> val;
            pushLEQ(right, left - 1, val);
            max = std::max(max, std::max(left, right));
        }
        for (int_t i = 1; i <= max; i++)
        {
            pushLEQ(i - 1, i, -1);
            pushLEQ(i, i - 1, 0);
            graph[SOURCE].push_back(Edge(i, 0));
            // cout << 0 << " " << i << " 0 " << endl;
        }
        SPFA();
        // return SPFA();
        return dis[max];
    }
    void SPFA()
    {
        std::fill(dis, dis + 1 + LARGE, -INF);
        std::fill(inq, inq + 1 + LARGE, false);
        std::queue<int_t> queue;
        queue.push(SOURCE);
        dis[SOURCE] = 0;
        inq[SOURCE] = true;
        while (queue.empty() == false)
        {
            auto front = queue.front();
            queue.pop();
            inq[front] = false;
            for (auto &edge : graph[front])
            {
                if (dis[front] + edge.weight > dis[edge.to])
                {
                    dis[edge.to] = dis[front] + edge.weight;
                    if (inq[edge.to] == false)
                    {
                        inq[edge.to] = true;
                        queue.push(edge.to);
                    }
                }
            }
        }
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        auto p = new Processor;
        cout << p->process() << endl;
        delete p;
    }
    return 0;
}