Loading...

洛谷P1250 种树

check评论:0 条 remove_red_eye浏览量:387 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-31

差分约束系统裸题
我们设$a[i]$代表前$i$个地方种了多少棵树
则对于每一个区间$[l,r]$若至少种植$k$棵树,可以得到不等式$a[r]-a[l-1] \geq k$,即$a[r] \geq a[l-1]+k$,则从$l-1$向$r$连一条长度为$k$的单向边即可
我们还需要其他的条件,易得$a[k-1] \geq a[k]-1$,$a[k] \geq a[k-1]$
所以每个点$i$都向$i+1$连一条长度为$0$的边,$i+1$向$i$连一条长度为$-1$的边($i \in [1,n]$)
最后利用这个性质,跑一遍最长路即可
code:

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct edge
{
    int next,to,dis;
}e[120010];
int dis[30010],vis[30010],cnt,head[30010];
queue<int> q;
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
int minn=0x3f3f3f3f;
int maxn=-0x3f3f3f3f;
int spfa()
{
    fill(dis+minn,dis+maxn+2,-0x3f3f3f3f);
    vis[minn]=1;
    dis[minn]=0;
    q.push(minn);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]<dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[maxn+1];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        maxn=max(maxn,y);
        minn=min(minn,x); 
        add(x,y+1,z);
    }
    for(int i=minn;i<=maxn;i++)
    {
        add(i,i+1,0);
        add(i+1,i,-1);
    }
    cout<<spfa();
} 

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名