西瓜种植

题目限制

时间限制	内存限制	评测方式	题目来源
1000ms	131072KiB	标准比较器	Local

题目背景

笨笨：小西瓜，小西瓜~
路人甲：不会呀，这西瓜明明就大着啊……
笨笨：那……大西瓜，大西瓜~
路人甲：这么快就改口了……
笨笨：西瓜西瓜~可爱的西瓜~

题目描述

笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……
  笨笨在一番研究过后，得出了m个结论，这m个结论可以使他收获的西瓜最多。
  笨笨的结论是这样的：
  从西瓜地B处到E处至少要种植T个西瓜，这个范围的收获就可以最大化。
  笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。

输入格式

第一行两个数n,m（0<n<=5000,0<=m<=3000），表示笨笨的西瓜地长n，笨笨得出m个结论。
接下来m行表示笨笨的m个结论，每行三个数b,e,t（1<=b<=e<=n,0<=t<=e-b+1）。

输出格式

输出笨笨最少需种植多少西瓜。

提示

基本上来说，笨笨的西瓜地就是一条壮观的线……笨笨原创。

样例数据

　　分析：

　　本来这题和$POJ1201$是一样的，但是输入格式不同，于是导致了我们本校$OJ$上出现一堆玄学错误。。。哎，不说了不说了，直接上代码。

　　Code：

//It is made by HolseLee on 25th Aug 2018

//JOYOI watermelon

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<iomanip>

#include<algorithm>

#include<vector>

#include<queue>

#define Max(a,b) (a)>(b)?(a):(b)

#define Min(a,b) (a)<(b)?(a):(b)

using namespace std;

const int N=;

int n,m,dis[N];

bool vis[N];

struct Edge{

    int to,val;

    Edge(const int &x,const int &y):to(x),val(y) {}

};

vector<Edge>e[N];

queue<int>t;

inline int read()

{

    char ch=getchar();int num=;

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<=''){

        num=(num<<)+(num<<)+(ch^);

        ch=getchar();

    }

    return num;

}

void spfa()

{

    for(int i=;i<=n;++i)dis[i]=-1e9;

    t.push();dis[]=;vis[]=;

    int x,y;

    while(!t.empty()){

        x=t.front();t.pop();

        vis[x]=;

        for(int i=;i<e[x].size();++i){

            y=e[x][i].to;

            if(dis[y]<dis[x]+e[x][i].val){

                dis[y]=dis[x]+e[x][i].val;

                if(!vis[y])t.push(y),vis[y]=;

            }

        }

    }

}

int main()

{

    n=read(),m=read();

    int x,y,z;

    for(int i=;i<=m;++i){

        x=read(),y=read(),z=read();

        e[x-].push_back(Edge(y,z));

    }

    for(int i=;i<=n;++i){

        e[i-].push_back(Edge(i,));

        e[i].push_back(Edge(i-,-));

    }

    spfa();

    printf("%d\n",dis[n]);

    return ;

}

西瓜

JOYOI 西瓜种植 [差分约束系统]