POJ1201:Intervals（差分约束）

　　差分约束经典题。设s[i]为前缀和，则有

　　s[i]-s[i-1]<=1 （i往i-1连-1的边）

　　s[i]>=s[i-1]　（i-1往i连0的边）

　　s[b]-s[a-1]>=c （a-1往b连c的边）

　　最小值就改>=然后跑最长路

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre,sum;}e[maxn];

int n,m,x,y,z,front,rear,tot,mx,mn;

ll dist[maxn],ans;

int h[maxn],v[maxn],last[maxn],tim[maxn];

bool flag;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void spfa()

{

    for(int i=mn;i<=mx;i++)v[i]=,dist[i]=-inf;

    dist[mn]=;v[mn]=;front=rear=;h[++rear]=mn;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now],too=e[i].too;i;i=e[i].pre,too=e[i].too)

        if(dist[too]<dist[now]+e[i].sum)

        {

            dist[too]=dist[now]+e[i].sum;

            if(++tim[too]>){printf("-1");flag=;return;}

            if(!v[too])

            {

                v[too]=;h[++rear]=too;

                if(rear==maxn)rear=-;

            }

        }

        v[now]=;

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        memset(last,,sizeof(last));

        memset(dist,,sizeof(dist));

        flag=;mx=-inf;mn=inf;

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

        {

            read(x);read(y);read(z);

            mx=max(mx,y);mn=min(mn,x);

            add(x-,y,z);

        }

        mn--;

        for(int i=mn;i<mx;i++)add(i,i+,),add(i+,i,-);

        spfa();

        if(flag)continue;

        printf("%lld\n",dist[mx]);

    }

    return ;

}