种西瓜

雨点打透心脏的1/2处 2021-11-05 09:18 290阅读 0赞

题目描述

笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……  
笨笨在一番研究过后，得出了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）。

输出

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

样例输入

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

样例输出

提示

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

解析：

这道题和我之前发的种树的题题目完全一样，但是这次我要用新学的方法AC它！

简单讲一下我的新方法：差分约束！！！

这个方法的大体思路是将不等式转化为最短路或最长路求解。

来看这几个条件：

条件1 u1-v1>=c

条件2 u2-v2<=c

可以用最长路来解决：

将1转化为：u1 >= v1 + c 可以建边v1--->u1=c

将2转化为：v2 >= u2 - c 可以建边u2--->v2=-c

然后在这个图中做SPFA求最短路就行了

最后上代码：

#include <bits/stdc++.h>
    using namespace std;
    const int INF=1e9;
    struct Edge
    {
        int now;
        int to;
        int next;
        int val;
    }e[3*50005];
    int head[50005];
    int d[50005];
    int vis[50005];
    int n,max_n,min_n;
    int tot=1;
    void add(int x,int y,int z)
    {
        e[tot].now=x;
        e[tot].to=y;
        e[tot].val=z;
        e[tot].next=head[x];
        head[x]=tot++;
    }
    void SPFA()
    {
        for(int i=min_n;i<=max_n;i++)
        {
            d[i]=-INF;
        }
        d[min_n]=0;
        queue<int> q;
        q.push(min_n);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            vis[x]=0;
            for(int i=head[x];i;i=e[i].next)
            {
                if(d[e[i].to]<d[x]+e[i].val)
                {
                    d[e[i].to]=d[x]+e[i].val;
                    if(!vis[e[i].to])
                    {
                        q.push(e[i].to);
                        vis[e[i].to]=1;
                    }
                }
            }
        }
    }
     
    int main()
    {
        scanf("%d",&n);
        min_n=INF;  
        max_n=-INF;
        for(int i=1;i<=n;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v+1,w);
            min_n=min(min_n,u);
            max_n=max(max_n,v+1);
        }
        for(int i=min_n;i<max_n;i++)
        {
            add(i,i+1,0);
            add(i+1,i,-1);
        }
        //for(int i=1;i<=tot;i++) printf("%d %d %d\n",e[i].now,e[i].to,e[i].val);
        SPFA();
        printf("%d\n",d[max_n]);
        return 0;
    }

转载于:https://www.cnblogs.com/chen-1/p/11207926.html