【洛谷P1250 种树】 解题报告

题目描述

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

写一个程序完成以下工作：

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例：

input

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

output

5

思路：

差分约束！！！！！！
不难发现 :

1. [l, r]至少要种T棵树 可以转换为Sum® - Sum(l-1) >= T

（sum_i是前缀和，即从1到i有多少棵树）

1. Sum(i) - Sum(i-1) <= 1

   Sum(i-1) - Sum(i) <= 0

1是从题目中所给信息得出的，而2是常识很多差分约束系统中一般都要加上的。
所以，即按照上面的信息建边,因为题目保证有解，所以放心地跑最短路就好啦！

Codes:

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

const int maxn = 30005,INF=1e9;
int n,h;
struct Edge
{
    int from,to,dis;
}e[maxn<<2];
int head[maxn],cnt,vis[maxn],d[maxn];

inline void add(int u,int v,int w)
{
    e[++cnt].from=head[u];
    e[cnt].to=v;
    e[cnt].dis=w;
    head[u]=cnt;
}

queue<int> q;
inline void spfa(int s)
{
    for(int i=0;i<=n;i++)
        d[i]=INF;
    q.push(s);vis[s]=1;d[s]=0;
    while(!q.empty()){
        int x=q.front();vis[x]=0;q.pop();
        for(int i=head[x];i;i=e[i].from){
            int y=e[i].to;
            if(d[y] > d[x] + e[i].dis){
                d[y]=d[x]+e[i].dis;
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    scanf("%d",&h);
    int S=n+1;
    for(int i=0;i<=n;i++) add(S,i,0);
    for(int i=1;i<=h;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(y,x-1,-z);
    }
    for(int i=1;i<=n;i++){
        add(i-1,i,1);
        add(i,i-1,0);
    }
    int Min=INF;
    spfa(S);
    for(int i=0;i<=n;i++) Min=min(Min,d[i]);
    printf("%d\n",d[n]-Min);
    return 0;
}

可能你也会有和我相同的疑惑：什么时候跑最长路，什么时候跑最短路(可能是我太菜了)。经过我的一番摸♂索，发现如果你连的边的意义是起始点加上边权小于等于到达点，那么就是跑最短路，反之，跑最长路。（可能是这样吧）。