洛谷 P1250 种树 题解

差分约束系统，维护前缀和，根据式子d[ b ] < = d[ e + 1 ] - t，可以看出要连e和b - 1，但占用了超级源点0，所以要把区间向后移，这样就可以用超级源点0来保持图的连通性（也可

以用n + 1作为超级源点，就不用了后移了）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define INF 2139062143

 #define maxnn 50010

 #define maxm 301000

 using namespace std;

 int n,m,maxnum=-,minnum=INF;

 struct node

 {

     int u,v,w,nex;

 }edge[maxm];

 int head[maxnn],cnt=;

 int dis[maxnn];

 bool vis[maxnn];

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void add(int x,int y,int z)

 {

     cnt++;

     edge[cnt].u=x;

     edge[cnt].v=y;

     edge[cnt].w=z;

     edge[cnt].nex=head[x];

     head[x]=cnt;

 }

 inline void spfa(int s)

 {

     memset(dis,,sizeof(dis));

     queue<int> q;

     q.push(s);

     vis[s]=;dis[s]=;

     while(!q.empty())

     {

         int now=q.front();

         q.pop();

         vis[now]=;

         for(int i=head[now];i!=-;i=edge[i].nex)

         {

             int to=edge[i].v;

             if(dis[now]+edge[i].w<dis[to])

             {

                 dis[to]=dis[now]+edge[i].w;

                 if(!vis[to])

                 {

                     vis[to]=;

                     q.push(to);

                 }

             }

         }

     }

 }

 int main()

 {

     int maxn=-;

     memset(head,-,sizeof(head));

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

     n++;

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

     {

         int b,e,t;

         b=read();e=read();t=read();

         b++;e++;

         add(e,b-,-t);  //d[b]<=d[e+1]-t

         maxn=max(maxn,e);

     }

     for(int i=;i<=maxn;i++)

     {

         add(i-,i,);//d[i]<=d[i-1]+1

         add(i,i-,);//d[i-1]<=d[i]

     }

     for(int i=;i<=maxn;i++)add(,i,);

     spfa();

     int minn=INF;

     for(int i=;i<=n;i++)minn=min(minn,dis[i]);

     printf("%d",dis[maxn]-minn);

     return ;

 }

请各位大佬斧正