[JOYOI] 1415 西瓜种植

题目描述

  笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……

  笨笨在一番研究过后，得出了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）。

输出格式

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

提示

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

样例数据

输入样例 #1 输出样例 #1

9 4

1 4 2

4 6 2

8 9 2

3 5 2

5

差分约束系统

习惯用最长路，对于xi-xj>=w 从j向i连w的边

重点是约束关系的推导，比如这题就有隐含条件一个地只能种一个西瓜

//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=50000;

int n,m;

struct Edge{

    int next,to,w;

}e[MAXN];

int ecnt,head[MAXN];

inline void add(int x,int y,int w){

    e[++ecnt].next = head[x];

    e[ecnt].to = y;

    e[ecnt].w = w;

    head[x] = ecnt;

}

int val[MAXN];

bool inq[MAXN];

void spfa(){

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

        val[i]=-(1<<28);

    queue<int> Q;

    Q.push(0);

    inq[0]=1;

    while(!Q.empty()){

        int top=Q.front() ;

        Q.pop();inq[top]=0;

        for(int i=head[top];i;i=e[i].next){

            int v=e[i].to ;

            if(val[v]<val[top]+e[i].w){

                val[v]=val[top]+e[i].w;

                if(!inq[v]) Q.push(v),inq[v]=1;

            }

        }

    }

}

int main(){

    cin>>n>>m;

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

        int x,y,w;

        cin>>x>>y>>w;

        add(x-1,y,w);

    }

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

        add(i-1,i,0);

        add(i,i-1,-1);

    }

    spfa();

        cout<<val[n];

    return 0;

}

巴特西

[JOYOI] 1415 西瓜种植

最新文章

热门文章