poj 1201差分制約

Zの中でi以下の要素の個数をs[i]で表すと、Zの中で区間[ai,bi]の中の要素の個数の授業はs[bi]-s[ai-1]と表すので、各s[i]を頂点として、差分制約に基づいてエッジを作成することができます.
制約:1.s[j]-s[i]>=c(既知条件)2.s[i]-s[i-1]>=0 3.s[i]-s[i-1]<=1
ここでは,制約条件2と3に表示されないエッジを格納する空間記憶上の最適化と,1回のループで1つのエッジが変更されなければ,直接ループから飛び出す時間的な最適化を行うことができる.

#include<iostream>
#include<cstdio>

using namespace std;
struct
{
   int u,v,w;
}e[50005];
int d[50005];

bool relax(int u,int v,int w)
{
    if(d[u]+w<d[v])
    {
        d[v]=d[u]+w;
        return true;
    }
    return false;
}

bool Bellman_Ford(int n,int m)
{
    int i,j;
    bool state;
    for(i=0;i<=n;i++)
        d[i]=0;
    for(i=0;i<n;i++)
    {
        state=false;
        for(j=0;j<m;j++)
            if(relax(e[j].u,e[j].v,e[j].w))
                state=true;
        for(j=1;j<=n;j++)
        {
            if(relax(j,j-1,0))
                state=true;
            if(relax(j-1,j,1))
                state=true;
        }
        if(!state)
            break;
    }
    return true;
}

int main()
{
    int n,min,max;
    while(~scanf("%d",&n))
    {
        min=50000;
        max=0;
        int a,b,c;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            e[i].u=b;
            e[i].v=a-1;
            e[i].w=-c;
            if(a<min)
                min=a;
            if(b>max)
                max=b;
        }
        Bellman_Ford(max,n);
        printf("%d
",d[max]-d[min-1]);
    }
    return 0;
}