POJ1201 Intervals <差分约束系统>

Problem

Intervals

Description

You are given $n$ closed, integer intervals $[a_i, b_i]$ and $n$ integers $c_1\sim c_n$.
Write a program that:
reads the number of intervals, their end points and integers $c_1\sim c_n$ from the standard input, computes the minimal size of a set $Z$ of integers which has at least $c_i$ common elements with interval $[a_i, b_i]$, for each $i=1,2,\cdots ,n$, writes the answer to the standard output.

Input

The first line of the input contains an integer $n$ ($1\le n\le 5\times 10^4$) – the number of intervals. The following n lines describe the intervals. The $(i+1)^{th}$ line of the input contains three integers $a_i$, $b_i$ and $c_i$ separated by single spaces and such that $0\le a_i\le b_i\le 5\times 10^4$ and $1\le c_i\le b_i - a_i+1$.

Output

The output contains exactly one integer equal to the minimal size of set $Z$ sharing at least $c_i$ elements with interval $[a_i, b_i]$, for each $i=1,2,\cdots ,n$.

Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

标签：差分约束系统

Translation

给出$n$个区间，试确定一个集合使得对于$i=1\sim n$，第$i$个区间内至少有$c_i$个数，并使得此集合尽量小，输出最小大小。

Solution

首先用前缀和。$sum[i]$表示从$1$到$i$中共选出多少个数到集合中。这样对于集合$[a_i,b_i]$，有$sum[b_i]-sum[a_i-1]\ge c_i$，于是我们可以从点$a_i-1$到$b_i$连一条权值为$c_i$的边。因为题意是要满足所有的边，所以我们需要找最长路。
此题有一些细节问题。首先，找最长路需要起点和终点，我们需要找到这些集合覆盖的范围，即找到左端点（其实应该是左端点$-1$）的最小值$s$和右端点的最大值$t$，找$s$到$t$的最大值。此外，光有上述的那些边时无法构成一个连通图的，所以我们需要找一些隐含条件。可以发现有$sum[i]-sum[i-1]\ge 0$，$sum[i]-sum[i-1]\le 1$，为了保持一致，应将后面的式子转化为大于等于，即$sum[i-1]-sum[i]\ge -1$，这样对于$i=s+1\sim t$，从$i-1$到$i$连接一条权值为$0$的路，从$i$到$i-1$连接一条权值为$-1$的路，之后就可以直接用$SPFA$找最长路了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 50000
using namespace std;
int n, cnt, s, t, pre[MAX_N+5], dis[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_N*3+5];
void insert(int u, int v, int c) {
    E[++cnt].v = v, E[cnt].c = c;
    E[cnt].nxt = pre[u], pre[u] = cnt;
}
void SPFA() {
    queue <int> que;
    bool inque[MAX_N+5];
    memset(dis, 128, sizeof(dis));
    memset(inque, 0, sizeof(inque));
    dis[s] = 0;
    que.push(s), inque[s] = true;
    while (!que.empty()) {
        int u = que.front();
        for (int i = pre[u]; i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (dis[u]+c > dis[v]) {
                dis[v] = dis[u]+c;
                if (!inque[v])	que.push(v), inque[v] = true;
            }
        }
        que.pop(), inque[u] = false;
    }
}
int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 0, s = 50000, t = 0;
        memset(pre, 0, sizeof(pre));
        memset(E, 0, sizeof(E));
        for (int i = 0; i < n; i++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            insert(u, v+1, c);
            s = min(s, u);
            t = max(t, v+1);
        }
        for (int i = s; i < t; i++)	insert(i, i+1, 0), insert(i+1, i, -1);
        SPFA();
        printf("%d\n", dis[t]);
    }
    return 0;
}