Portal

Portal1: Luogu

Description

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成$1 \cdots N$。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码$B, E, T$。这三个数表示该居民想在$B$和$E$之间最少种T棵树。当然，$B \le E$，居民必须记住在指定区不能种多于区域地块数的树，所以$T \le E - B + 1$。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

Input

第一行包含数据$N$，区域的个数$(0 < N \le 30000)$；

第二行包含$H$，房子的数目$(0 < H \le 5000)$；

下面的$H$行描述居民们的需要：B E T，$0 < B \le E \le 30000，T \le E - B + 1$。

Output

输出文件只有一行写有树的数目。

Sample Input

9
4
1 4 2
4 6 2
8 9 2
3 5 2

Sample Output

5

Solution

这题差分约束，我们用$\mathrm{s[i]}$表示从第$1$号到第$i$号的树的数量的和（也就是前缀和）。

那么题目中的约束条件就是：

1. $s[E] - s[B - 1] \ge T$

因为事前缀和，所以还隐含了：

1. $s[i] - s[i - 1] \le 1$

2. $s[i - 1] \le s[i]$

还有每个位置的树的数量都是大于$0$的数，所以还有：

1. $s[i] \le s[n + 1] + 0$（把$n + 1$号位置设置为超级源）

整理可得：

1. $s[B - 1] \le s[E] - T$

2. $s[i] \le s[i - 1] + 1$

3. $s[i - 1] \le s[i] + 0$

4. $s[i] \le s[n + 1] + 0$

然后跑最长路。

这样，这道题就解决了。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f, MAXN = 200005;
struct EDGE {
    int to, nxt, val;
} edge[MAXN];
int n, m, u, v, opt, val, cnt, vis[MAXN], dis[MAXN], head[MAXN];
inline void addedge(int u, int v, int val) {//邻接表存图
    edge[++cnt].to = v; edge[cnt].val = val; edge[cnt].nxt = head[u]; head[u] = cnt;
}
inline void SPFA(int cur) {
    queue<int> Q;
    Q.push(cur);
    for (int i = 0; i <= n + 1; i++)
        dis[i] = 1;
    vis[cur] = 1;
    dis[cur] = 0;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].val) {
                dis[v] = dis[u] + edge[i].val;
                if (!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &val);
        addedge(v, u - 1, -val);
    }
    for (int i = 0; i <= n; i++)
        addedge(n + 1, i, 0);
    for (int i = 1; i <= n; i++) {
        addedge(i - 1, i, 1);
        addedge(i, i - 1, 0);
    }
    SPFA(n + 1);//最长路
    int Min = INF;
    for (int i = 0; i <= n; i++)
        Min = min(Min, dis[i]);
    printf("%d\n", dis[n] - Min);
    return 0;
}