P1250 种树

题目描述：

n个点，每个点最多种一棵树，m个要求(b, c, t)，表示b到c区间中至少种t棵树，求能满足条件所需要的最少的树的数量

思路：

求最小值，用最长路，用大于号

将树的数组a，进行求前缀和的操作，可以将m个条件转换成 $sum[c] - sum[b - 1] >= t$，进而转化成 $sum[c] >= sum[b - 1] + t$,y也就是从b-1到c建立一条权值为t的边

为了满足每个点只能种一棵树的条件，我们可以根据这个性质列出这个关系式$0<=sum[i] - sum[i - 1]<=1$,也就是 $sum[i]>=sum[i-1] + 0$和 $sum[i - 1] >= sum[i] - 1 -1$，也就是从i-1到i建立一条权值为0的边，从i到i-1建立一条权值为-1的边

再就是建立一个超级源点，从0到i建立一条权值为0的边，然后跑单源最长路就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int a, b, c;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool vis[MAX];
int dis[MAX];

void SPFA(){
    queue<int>q;
    for(int i = 0; i <= n; ++i){
        q.push(i);
        vis[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    cout << dis[n] << endl;
}

void work(){
    cin >> n >> m;
    while (m--) {
        cin >> a >> b >> c;
        add(a - 1, b, c);
    }
    for(int i = 1; i < n; ++i){
        add(i + 1, i, -1);
        add(i, i + 1, 0);
    }
    SPFA();
}

int main(){
    io;
    work();
    return 0;
}