poj 1201 差分约束+SPFA

/*
s[b+1]-s[a]>=c
s[i+1]-s[i]>=0
s[i]-s[i+1]>=-1
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 50005
struct node
{
    int v,w,next;
}edge[maxn<<2];

int id,end,st;
int a,b,c,n;
int head[maxn];
bool in[maxn];
int d[maxn];
void init()
{
    memset(head,-1,sizeof(head));
    end=id=0;
    st=0x3f3f3f3f;
}
void addedge(int a,int b,int c)
{
    edge[id].v=b;
    edge[id].w=c;
    edge[id].next=head[a];
    head[a]=id++;
}
void SPFA()
{
    queue<int> Q;
    memset(in,0,sizeof(in));
    memset(d,-0x3f,sizeof(int)*(end+5));
    Q.push(0);
    in[0]=1;
    d[0]=0;
    int tmp;
    while(!Q.empty())
    {
        tmp=Q.front();Q.pop();
        in[tmp]=0;
        for(int i=head[tmp];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v]<d[tmp]+edge[i].w)
            {
                d[edge[i].v]=d[tmp]+edge[i].w;
                if(!in[edge[i].v])
                {
                    in[edge[i].v]=1;
                    Q.push(edge[i].v);
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b+1,c);
            end=max(end,b+1);
        }
        for(int i=0;i<end;i++)
        {
            addedge(i,i+1,0);
            addedge(i+1,i,-1);
        }
        SPFA();
        printf("%d\n",d[end]);
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：poj1160 Post Office
下一个：POJ 3080 Blue Jeans 暴力枚举+KMP