题目描述 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成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。

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

输入输出样例

输入样例1：

9

4

1 4 2

4 6 2

8 9 2

3 5 2

输出样例1：

5

代码

#include
    
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           using namespace std; int n,m,ans; bool u[30000]; struct Edge{ int x,y,z; }a[30000]; bool cmp(Edge a,Edge b){ return a.y
          
           =a[i].z){ continue;} for(int k=a[i].y;k>=a[i].x;k--){ if(!u[k]){ ans++; sum++; u[k]=1; if(sum==a[i].z){ break;} } } } printf("%d",ans); return 0; }
          
         
        
       
      
     
    

用单源最短路，并记录是否种植过了。