HDU - 1384 Intervals （差分约束 spfa最长路）

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.

Write a program that:

> reads the number of intervals, their endpoints and integers c1, ..., cn from the standard input,

> computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i = 1, 2, ..., n,

> writes the answer to the standard output

Input

The first line of the input contains an integer n (1 <= n <= 50 000) - the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <= ci <= bi - ai + 1.

Process to the end of file.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.

Sample Input

Sample Output

题意：

给定n个区间，每个区间内至少选中c个点，问整个数轴上至少选中多少个点

思路：

前几个月学的，比赛的时候竟然没有看出来qwq 枯了

当时写的博客https://blog.csdn.net/weixin_43871207/article/details/102484592

差分约束典型例题

设[0，i]共选中了d[i]个点，可以得出d[b] - d[a - 1] >= c，对于每个不等式建立一条从a - 1到b，权值为ci的边。

注意隐含条件：每个点至少选0次（即不选），至多选1次，所以除了对输入的多个区间建边外，还有d[i] - d[i - 1] >= 0 和d[i] - d[i -1] <= 1，将第二个不等式转化为上面的形式即d[i - 1] - d[i] >= -1

防止数组越界，将所有数+1

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int inf = 0xc0c0c0c0;
const int N = 5e4 + 20;

int tot, n, r;
int dis[N], vis[N], head[N], num[N];

struct Edge
{
    int u, v, w, next;
}edge[10 * N];

void add(int a, int b, int c)
{
    edge[tot].u = a;
    edge[tot].v = b;
    edge[tot].w = c;
    edge[tot].next = head[a];
    head[a] = tot++;
}

bool spfa(int s)
{
    queue<int>q;
    for(int i = 0; i <= r + 2; ++i)
        dis[i] = inf;
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    q.push(s);
    dis[s] = 0;
    while(!q.empty())
    {
        int pos = q.front();
        q.pop();
        vis[pos] = 0;
        num[pos]++;
        for(int i = head[pos]; i != -1; i = edge[i].next)
        {
            if(dis[edge[i].v] < dis[edge[i].u] + edge[i].w)
            {
                dis[edge[i].v] = dis[edge[i].u] + edge[i].w;
                if(!vis[edge[i].v])
                {
                    vis[edge[i].v] = 1;
                    q.push(edge[i].v);
                    if(num[edge[i].v] >= r)
                        return 0;
                }
            }
        }
    }
    return 1;
}
int main()
{
    int a, b, c;
    while(~scanf("%d", &n))
    {
        tot = 0;
        memset(edge, 0, sizeof(edge));
        memset(head, -1, sizeof(head));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            r = max(b, r);    ///最大值
            add(a, b + 1, c);
        }
        for(int i = 2; i <= r + 1; ++i)
        {
            add(i - 1, i, 0);
            add(i, i - 1, -1);
        }
        bool flag = spfa(1);    ///是否有正环（在本题中并不重要）
        if(flag && dis[r + 1] == inf)
            flag = 0;
        if(flag)
        {
            cout<<dis[r + 1]<<'\n';
        }
    }
    return 0;
}