Intervals

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1708 字
差分约束建图后跑最长路
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1509
// 题意：给 n 个闭区间 [a, b] 与至少选 c 个数的要求，求满足所有区间的最少整数个数。
// 思路：差分约束。设 S(i) 为 [0, i] 中选的数的个数，区间条件是 S(b) - S(a - 1) >= c，再用 0 <= S(i) - S(i - 1) <= 1 串起来，跑最长路。
// 1. 下标整体加 1，避免出现 S(-1)，节点 0 对应 S(-1)，节点 x + 1 对应 S(x)。
// 2. 答案是源点 0 到节点 maxb + 1 的最长路长度，也就是各下界累加后的最小可行值。
// 复杂度：O(k * V) 时间 / O(V) 空间，V = 50002
// 易错点：相邻约束要双向建边（上界 1 对应反向边 -1），只建正向边答案会偏小。
// 易错点：区间的 a 可能为 0，必须靠整体平移来规避负下标，不能直接写成 a - 1。
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 50005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[MAXV];
int dis[MAXV];
bool inq[MAXV];
int main(){
    int n;
    if(!(cin >> n)) return 0;
    int mx = 0;
    for(int i = 0; i < n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        Edge e;
        e.to = b + 1;
        e.w = c;
        g[a].push_back(e);
        if(b > mx) mx = b;
    }
    for(int i = 0; i <= mx; i++){
        Edge up;
        up.to = i + 1;
        up.w = 0;
        g[i].push_back(up);
        Edge down;
        down.to = i;
        down.w = -1;
        g[i + 1].push_back(down);
    }
    for(int i = 0; i <= mx + 1; i++){
        dis[i] = -INF;
    }
    queue<int> q;
    dis[0] = 0;
    inq[0] = true;
    q.push(0);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int w = g[u][i].w;
            if(dis[v] < dis[u] + w){
                dis[v] = dis[u] + w;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    cout << dis[mx + 1] << "\n";
    return 0;
}
Intervals

正文

一本通·提高篇的其它内容
